使用一组有限的操作对2个50000个数字的链接列表进行排序 [英] Sorting 2 linked list of 50000 numbers with a limited set of operations
问题描述
因此，我有一个上学的项目:我有一个链接列表，其中包含50000个数字，第二个空白列表.我的说明面板非常有限.他们是:
So I have this project for school : I have a linked list of 50 000 numbers and a second empty list. I only have a very limited panel of instructions. They are :
-
"sa"交换列表1的前两个元素
"sa" swaps the first two elements of list 1
"sb"交换列表2的前两个元素
"sb" swaps the first two elements of list 2
"ss"同时是"sa"和"sb"
"ss" is "sa" and "sb" at the same time
"pa":将列表2的顶部元素推到列表1顶部
"pa" : push top element of list 2 on top of list 1
"pb":将列表1的顶部元素推到列表2顶部
"pb": push top element of list 1 on top of list 2
"ra":旋转列表1(第一个元素变为最后一个元素)
"ra": rotate list 1 (first element becomes last)
"rb":旋转列表2(第一个变为最后一个)
"rb":rotate list 2 (first becomes last)
"rr":同时为"ra"和"rb"
"rr": "ra"and "rb" at once
"rra":旋转列表1(最后一个排在第一位)
"rra": rotate list 1 (last becomes first)
"rrb":旋转列表2(最后成为第一)
"rrb": rotate list 2(last becomes first)
"rrr":同时显示"rra"和"rrb"
"rrr": "rra" and "rrb" at once
我必须在c中实现一种排序算法，目标是用最少的指令数来完成它. 我尝试了一种非常简单的算法，将列表一旋转到最大值为止，然后反复将其推入列表2中，直到所有内容都进入列表2，然后再将所有内容推回列表1中，但是我无法对更多列表进行排序在合理的时间内超过5k个数字
I have to implement a sorting algorithm in c and the goal is to do it with the smallest amount of instructions. I tried with a very simple algorithm that rotated list one until the maximum was on top and then pushed it in list 2 repeatedly until everything was in list 2 and then pushed everything back in list 1, but I was not able to sort lists of more than 5k numbers in a reasonable amount of time
推荐答案
我想我已经弄清楚了如何使用快速排序来做到这一点.这是一些伪代码.
I think I've figured out how to do this using quick sort. Here's some pseudocode.
更新了伪代码，使其专注于正在执行的操作，而不是不必要的语法
edit: updated pseudocode to focus on what it's doing and not unnecessary syntax
quicksort(int n)
if n == 1 return
int top_half_len = 0
choose a median //it's up to you to determine the best way to do this
for 0 to n { //filter all values above the median into list 2
if (value > median) {
push list 1 top to list 2 //list 2 stores the larger half
top_half_len++
}
rotate list 1 forward
}
//reverse the list back to original position
rotate list 1 backward (n - top_half_len) times
//push larger half onto smaller half
push list 2 top to list 1 top_half_len times
//recursively call this on the larger half
quicksort(top_half_len)
//rotate smaller half to front
rotate list 1 forward top_half_len times
//recursively call this on smaller half
quicksort(n - top_half_len)
//reverse list back to original position
rotate list 1 backward top_half_len times
基本上，它将列表分成小于或等于中位数的部分(较小的一半)和大于中位数的部分(较大的一半).然后，它将自己称为这两个部分.一旦长度为1，就对算法进行了处理，因为对长度列表进行了排序. Google快速排序以获取实际说明.
Basically, it splits the list into a portion smaller or equal than the median (smaller half) and a portion greater than the median (larger half). Then it calls itself on both of these halves. Once they're length 1, the algorithm is done, since a 1 length list is sorted. Google quick sort for an actual explanation.
我认为这应该可行，但是我可能错过了一些极端情况.不要盲目跟随.另外，如果您要处理数组，我建议您在特定的递归深度停止快速排序，并使用堆排序(或使用某些方法来防止最坏情况下的O(n ^ 2)复杂性)，但是我不确定在这里什么是有效的. 更新:根据彼得·科德斯(Peter Cordes)的说法，当数组大小小于某个数组大小时，您应该使用插入排序(IMO，您也应该在某个递归深度上).
I'm think this should work, but I may have missed some edge case. Don't blindly follow this. Also, if you were dealing with arrays, I'd recommend you stop the quick sort at a certain recursion depth and use heap sort (or something to prevent the worst case O(n^2) complexity), but I'm not sure what would be efficient here. update: according to Peter Cordes, you should use insertion sort when you get below a certain array size (IMO you should at a certain recursion depth too).
显然，在链表上合并排序更快.修改它以实现合并排序可能并不难.合并排序与快速排序非常相似. 为什么合并排序优先于快速排序用于对链接列表进行排序
Apparently merge sort is faster on linked lists. It probably wouldn't be too hard to modify this to implement merge sort. Merge sort is pretty similar to quick sort. why is merge sort preferred over quick sort for sorting linked lists
这篇关于使用一组有限的操作对2个50000个数字的链接列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
