|
Stalin sort
|
|
Stalin sort is a stable sorting algorithm that works by iterating over the array of elements to be sorted and removing items that are "out of order" in the array to be sorted. It is a method to find the longest increasing subsequence in a given array. The sort is considered to be a humourous algorithm, not being intended to be used to sort in real-life applications. The algorithm can be described by the following pseudocode. function stalinSort(list A) is n = length(A) bigger = 0 B = empty list for i = 0 to n - 1 if A >= bigger THEN bigger = A B.push(A) return B Example Consider the unsorted array "1 2 5 3 10 4 7 6", to be sorted into increasing order. In each step, elements written in bold are being compared. In this example two items in the array need to be removed. # ( 1 2 5 3 10 4 ) → ( 1 2 5 3 10 4 ), Here the items being compared are in increasing order and hence are unchanged. # ( 1 2 5 3 10 4 ) → ( 1 2 5 3 10 4 ) # ( 1 2 5 3 10 4 ) → ( 1 2 5 10 4 ), Since 3 < 5, 3 is removed from the array. # ( 1 2 5 10 4 ) → ( 1 2 5 10 4 ) # ( 1 2 5 10 4 ) → ( 1 2 5 10 4 ), As 4 < 10, 4 is removed from the array. # ( 1 2 5 10), Here the algorithm terminates as the end of the array has been reached. 
|
| < Prev | Next > |
|---|
Main Menu
| Home |
| Articles |
| Search |
| Submit Article |
| Contact Us |
| Donate to Wikibin |
