name of a sorting algorithm
Hi, Could someone please tell me what the following sorting algorithm is called? Let an array contain the elements a_1, a_2, ..., a_N. Then: for i = 1 to N-1: for j = i+1 to N: if a_j a_i then swap(a_j, a_i) It's so simple that it's not mentioned anywhere. I guess it's called selection sort but I'm not sure. The minimum selection sort is an improvement of this one. Thanks, Laszlo -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
Jabba Laci wrote: Could someone please tell me what the following sorting algorithm is called? Let an array contain the elements a_1, a_2, ..., a_N. Then: for i in xrange (N-1): for j in xrange (i, N): if a[j] a[i]: a[i], a[j] = a[j], a[i] It's so simple that it's not mentioned anywhere. I guess it's called selection sort but I'm not sure. The minimum selection sort is an improvement of this one. It's what Wikipedia says a selection sort is: put the least element in [0], the least of the remaining elements in [1], etc. Mel. -- http://mail.python.org/mailman/listinfo/python-list
RE: name of a sorting algorithm
for i in xrange (N-1): for j in xrange (i, N): if a[j] a[i]: a[i], a[j] = a[j], a[i] It's what Wikipedia says a selection sort is: put the least element in [0], the least of the remaining elements in [1], etc. If your only requirement to match to selection sort is the end result, then every sort would be selection sort. If you meant put the least element in [0] in the first pass then that would indeed be selection sort, but that is not what the above code does. The above code is bubble sort. Ramit Ramit Prasad | JPMorgan Chase Investment Bank | Currencies Technology 712 Main Street | Houston, TX 77002 work phone: 713 - 216 - 5423 -- This email is confidential and subject to important disclaimers and conditions including on offers for the purchase or sale of securities, accuracy and completeness of information, viruses, confidentiality, legal privilege, and legal entity disclaimers, available at http://www.jpmorgan.com/pages/disclosures/email. -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
Am 14.02.2012 16:01, schrieb Jabba Laci: Could someone please tell me what the following sorting algorithm is called? Let an array contain the elements a_1, a_2, ..., a_N. Then: for i = 1 to N-1: for j = i+1 to N: if a_j a_i then swap(a_j, a_i) It's so simple that it's not mentioned anywhere. Please do your own homework. This code isn't even Python! I guess it's called selection sort but I'm not sure. You guessed right. Uli -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
On 14 February 2012 15:31, Dennis Lee Bieber wlfr...@ix.netcom.com wrote: On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci jabba.l...@gmail.com wrote: Could someone please tell me what the following sorting algorithm is called? Let an array contain the elements a_1, a_2, ..., a_N. Then: for i = 1 to N-1: for j = i+1 to N: if a_j a_i then swap(a_j, a_i) Off hand... The ancient Bubble-Sort... http://en.wikipedia.org/wiki/Bubble_sort Ahem... No, it's not Bubble Sort. Bubble sort only swaps adjacent terms. I don't know what this sort is called, if it even has a name. It's a kind of Selection Sort, as each pass it looks for the minimum of the remaining unsorted items. But it ruffles the unsorted list each pass, seemingly to save using an extra register to store the current minumum (there was a time when registers were at a premium). -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
RE: name of a sorting algorithm
Prasad, Ramit wrote: for i in xrange (N-1): for j in xrange (i, N): if a[j] a[i]: a[i], a[j] = a[j], a[i] It's what Wikipedia says a selection sort is: put the least element in [0], the least of the remaining elements in [1], etc. If your only requirement to match to selection sort is the end result, then every sort would be selection sort. If you meant put the least element in [0] in the first pass then that would indeed be selection sort, but that is not what the above code does. The above code is bubble sort. Well, the classic bubble sort swaps adjacent elements until the extreme one gets all the way to the end. This sort continually swaps with the end element during one pass until the end element holds the extreme. Then it shrinks the range and swaps then next less extreme into the new end element. It does extra swaps because it combines the swap operation with recording the temporary extreme while it searches the subrange. Mel. -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
On Feb 14, 8:22 am, Arnaud Delobelle arno...@gmail.com wrote: On 14 February 2012 15:31, Dennis Lee Bieber wlfr...@ix.netcom.com wrote: On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci jabba.l...@gmail.com wrote: Could someone please tell me what the following sorting algorithm is called? Let an array contain the elements a_1, a_2, ..., a_N. Then: for i = 1 to N-1: for j = i+1 to N: if a_j a_i then swap(a_j, a_i) Off hand... The ancient Bubble-Sort... http://en.wikipedia.org/wiki/Bubble_sort Ahem... No, it's not Bubble Sort. Bubble sort only swaps adjacent terms. I don't know what this sort is called, if it even has a name. It's a kind of Selection Sort, as each pass it looks for the minimum of the remaining unsorted items. But it ruffles the unsorted list each pass, seemingly to save using an extra register to store the current minumum (there was a time when registers were at a premium). -- Arnaud I disagree. In a bubble sort, one pointer points to the top element, while another descents through all the other elements, swapping the elements at the pointers when necessary. Then the one pointer moved down to the next element and the process repeats. This looks like the bubble sort to me. It was one of the first algorithms I had to program in my first programming class in 1969. Den -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
Den wrote: I disagree. In a bubble sort, one pointer points to the top element, while another descents through all the other elements, swapping the elements at the pointers when necessary. 'When I use a word,' Humpty Dumpty said, in rather a scornful tone, 'it means just what I choose it to mean — neither more nor less.' (_Through the Looking Glass, Lewis Caroll). And you, too, have that ability. Contrariwise see Knuth, _The Art of Computer Programming_ Section 5.2.2, Algorithm B. Mel. -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
On Tue, Feb 14, 2012 at 9:55 AM, Den patents...@gmail.com wrote: On Feb 14, 8:22 am, Arnaud Delobelle arno...@gmail.com wrote: On 14 February 2012 15:31, Dennis Lee Bieber wlfr...@ix.netcom.com wrote: On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci jabba.l...@gmail.com wrote: Could someone please tell me what the following sorting algorithm is called? Let an array contain the elements a_1, a_2, ..., a_N. Then: for i = 1 to N-1: for j = i+1 to N: if a_j a_i then swap(a_j, a_i) Off hand... The ancient Bubble-Sort... http://en.wikipedia.org/wiki/Bubble_sort Ahem... No, it's not Bubble Sort. Bubble sort only swaps adjacent terms. I don't know what this sort is called, if it even has a name. It's a kind of Selection Sort, as each pass it looks for the minimum of the remaining unsorted items. But it ruffles the unsorted list each pass, seemingly to save using an extra register to store the current minumum (there was a time when registers were at a premium). -- Arnaud I disagree. In a bubble sort, one pointer points to the top element, while another descents through all the other elements, swapping the elements at the pointers when necessary. Then the one pointer moved down to the next element and the process repeats. This looks like the bubble sort to me. It was one of the first algorithms I had to program in my first programming class in 1969. Either you're misremembering, or the algorithm you programmed 43 years ago was not actually bubble sort. Quoting from Wikipedia: Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements bubble to the top of the list. In the present algorithm, you'll note that elements in the unsorted part of the list do not bubble up as they would in bubble sort. Rather, they jump around somewhat randomly until they are finally selected for the current sort index. I agree with Arnaud -- this is a selection sort variant that saves a local variable (the index of the minimum element) by placing it at the current sort index instead -- at the cost of doing additional swaps. Probably not a good trade-off in Python (but then again, no pure Python sort algorithm is likely to perform better than the built-in). Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
Hi, Either you're misremembering, or the algorithm you programmed 43 years ago was not actually bubble sort. Quoting from Wikipedia: Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements bubble to the top of the list. I don't agree with the last sentence. During bubble sort, in the 1st pass the largest element is moved to the top (for me top means the right side (end) of an array). Thus the end of the array is sorted. In the 2nd pass, the largest element of the unsorted left part is moved to the end, etc. That is, it's the _larger_ elements that bubble to the top. At http://en.wikipedia.org/wiki/Bubble_sort you can find an animated gif that shows how the algorithm works. In the present algorithm, you'll note that elements in the unsorted part of the list do not bubble up as they would in bubble sort. Rather, they jump around somewhat randomly until they are finally selected for the current sort index. I agree with Arnaud -- this is a selection sort variant that saves a local variable (the index of the minimum element) by placing it at the current sort index instead -- at the cost of doing additional swaps. Probably not a good trade-off in Python (but then again, no pure Python sort algorithm is likely to perform better than the built-in). The minimum selection sort is an improvement of this noname algorithm. I give it in pseudo-code. Let A be an array with N elements. Indexing starts with 1. for i := 1 to N-1: minindex := i for j := i+1 to N: if A[j] A[minindex] then minindex := j end for if i != minindex then swap(A[i], A[minindex]) end for The two loops are the same as in the naive version. It will also sort the array from the left side. It does much less swaps than the naive version. If the noname algorithm is called selection sort, then its name can be misleading. One may ask OK, but which one? Minimum or maximum selection sort?. Well, neither... Laszlo -- http://mail.python.org/mailman/listinfo/python-list
RE: name of a sorting algorithm
Prasad, Ramit wrote: My apologies, you are correct. It is a selection sort, just an inefficient one. Hmm, I think I should say it is neither since it reminds me of a hybrid of both (bubble/selection). The swapping seems very bubble sort, but the looking for the min / max case seems selection sort-ish. Whatever it is, it is certainly inefficient. :) Ramit Ramit Prasad | JPMorgan Chase Investment Bank | Currencies Technology 712 Main Street | Houston, TX 77002 work phone: 713 - 216 - 5423 -- This email is confidential and subject to important disclaimers and conditions including on offers for the purchase or sale of securities, accuracy and completeness of information, viruses, confidentiality, legal privilege, and legal entity disclaimers, available at http://www.jpmorgan.com/pages/disclosures/email. -- http://mail.python.org/mailman/listinfo/python-list
RE: name of a sorting algorithm
Wilson, Mel wrote: Well, the classic bubble sort swaps adjacent elements until the extreme one gets all the way to the end. This sort continually swaps with the end element during one pass until the end element holds the extreme. Then it shrinks the range and swaps then next less extreme into the new end element. It does extra swaps because it combines the swap operation with recording the temporary extreme while it searches the subrange. My apologies, you are correct. It is a selection sort, just an inefficient one. Ramit Ramit Prasad | JPMorgan Chase Investment Bank | Currencies Technology 712 Main Street | Houston, TX 77002 work phone: 713 - 216 - 5423 -- This email is confidential and subject to important disclaimers and conditions including on offers for the purchase or sale of securities, accuracy and completeness of information, viruses, confidentiality, legal privilege, and legal entity disclaimers, available at http://www.jpmorgan.com/pages/disclosures/email. -- http://mail.python.org/mailman/listinfo/python-list
Re: name of a sorting algorithm
On Tue, Feb 14, 2012 at 11:10 AM, Jabba Laci jabba.l...@gmail.com wrote: Hi, Either you're misremembering, or the algorithm you programmed 43 years ago was not actually bubble sort. Quoting from Wikipedia: Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements bubble to the top of the list. I don't agree with the last sentence. During bubble sort, in the 1st pass the largest element is moved to the top (for me top means the right side (end) of an array). Thus the end of the array is sorted. In the 2nd pass, the largest element of the unsorted left part is moved to the end, etc. That is, it's the _larger_ elements that bubble to the top. At http://en.wikipedia.org/wiki/Bubble_sort you can find an animated gif that shows how the algorithm works. I think that by top they mean front. Each largest element in turn gets moved to the end in a single pass. It is the smaller elements gradually moving toward the front over many passes that I believe is described as bubbling, as can be seen in that gif. If the noname algorithm is called selection sort, then its name can be misleading. One may ask OK, but which one? Minimum or maximum selection sort?. Well, neither... It is a minimum selection sort, because it selects the minimum element on each pass. It just stores the minimum element so far in-place in the array, rather than in a separate variable. -- http://mail.python.org/mailman/listinfo/python-list
