This problem is inspired by the discussion about ordering specification, BSort
in the paper "Aurora: a new model and architecture for data stream management"
Problem:
There is an array A whose size is n. there is a ascending sorting with some
disorder in A. The disorder is specified as this:
For any element, there are at most 2 bigger preceding elements. In other words,
for A[i], A[i_1] > A[i], ..., A[i_m] > A[i] (i_1 > i, ..., i_m > i). m <= 2.
Design an algorithm to remove the disorder in A.
NOTE: 2 can be generalized to m.
Solution:
Run 2 bubble sort pass over A.
---------------
| | | |X| | | |
---------------
^
i
Since A[i-1] is the biggest element among the A[0..i-1], A[i-1] must be among
the 2 preceding elements which are bigger than A[i]. If A[i] >= A[i-1], there
will no preceding bigger elements for A[i]. Otherwise, switch A[i] with A[i-1].
There will be at most 1 preceding element for A[i-1]. So after the first pass,
for any element, there is at most 1 bigger preceding element.
Apply the similar analysis to pass 2. After the second pass, for any element,
there is at most 0 bigger preceding element. In other words, A is sorted.
分享到:
相关推荐
Data structure and algorithm concepts. In order to sort the large files bubble sort can be used
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是...
随机生成500个数,然后对这500数使用冒泡排序进行排序
python冒泡排序(Bubble Sort) 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换...
bubble sort algorithm
简单实例应用java 中的list 来实现bubble sort. txt文档输入, Console输出.
这是computer organization课上的bubble sort源程序,谢谢大家的支持。
sort,scratch2源码Bubble Sort-冒泡排序算法,sb2源文件内含冒泡排序算法代码有兴趣的同学可以下载研究
基于python的排序算法-冒泡排序Bubble Sort
This VI generates 1024 random numbers and sorts them with the bubble sort method.
冒泡排序 依次比较两个相邻的元素,如果前者大于后者就交换位置 每一趟排序之后就会把这趟中的最大值放在最后一位 重复上诉过程,直到没有在需要比较的元素为止
这是computer organization 课上的bubble sort的源程序第二版。
冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成
bubble_sort.exe
A simple Bubble Sort code that shows how the program works within a VB program.
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。...
Bubble Sort-冒泡排序算法-少儿编程scratch项目源代码文件案例素材.zip
bubble sort algorithm in vb.net
冒泡排序:重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成...
关于insertion sort, merge sort, quick sort 等。 USC Bill Cheng's PPT