0
$\begingroup$

Explain and compare selection, insertion and bubble sorts. Assume that your application (say a data base application) deals with large records where comparisons are performed by means of integer keys. Assume also that your application requires a stable sorting method, i.e. a method that does not change the relative ordering of elements that are equal. Which of these sorting methods would you choose, and why? (Hint: consider sorting based on the following integer keys 19, 14(1), 7, 12, 14(2), 10).

This is a question I'm studying in class, not sure which is the right one and why.

$\endgroup$
  • 2
    $\begingroup$ What are your thoughts on the question? What are some pros and cons of each algorithm? $\endgroup$ – Yuval Filmus Feb 27 '17 at 21:52
  • 1
    $\begingroup$ What considerations do you think might exist? What properties of those sorting algorithms do you know about that might be relevant? What efforts have you made to begin to approach this on your own? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Finally, what exactly is your question? All I see is a copy-paste of an exercise, but no question about it. $\endgroup$ – D.W. Feb 27 '17 at 23:01
1
$\begingroup$

A "database" that isn't ashamed of calling itself "database" will have hundreds of thousands or millions of records. Any algorithm where the number of operations is quadratic except for special cases is totally unsuitable. So the answer is "none of the above".

You'd do some serious measuring to decide whether to just create an in-memory index (that means you don't sort anything at all, but you just record #1 = 7 at record 3, #2 = 10 at record 6, ...), or use merge sort or Quicksort. Quicksort only if you have a backup, in case there's a problem during the sort.

$\endgroup$
0
$\begingroup$

If you want a complete algorithm/definition of these sorts, you can just google it, so instead I'm going to give you a brief explanation.

Bubble Sort

Say n is the current element being swapped. When the sort starts n is the first element in the array. The algorithm begins by comparing n to the element adjacent to the right of it, and if it is bigger then it swaps n with the element to the right of n. Then it continues down the line, comparing each element to the right of n, swapping whenever n is larger. If n is smaller, however, the current n stays where it is and we choose a new n to be the element to the right of the old n. Then we compare the new n with the element to the right. Once we get accross the entire array we start at the beginning again and choose n to be the first element in the array, then continue til the array is sorted.

Insertion Sort

For insertion sort we maintain a sorted section of the list, and an unsorted section. The sorted section is on the left of the list, unsorted on the right. When the sort begins the sorted section has no elements and the unsorted section has every element in the array. The algorithm works as follows: Pick the first element in the unsorted list, insert it in the correct position in the sorted list, repeat until there are no more elements in the unsorted list and we are left with just a sorted list.

Selection Sort

Here we create a sorted list by "selecting" elements from least to biggest, and swapping them into the correct place. First, we choose the smallest element in the array and swap it into the first spot in the array. Then the second smallest element and swap into the second spot. Then third smallest and so on, until we have a sorted list.

Performance

Straight from my data structures and algorithms teacher, bubble sort is a terrible sorting algorithm, so just don't even use it. Is the list nearly sorted or is it random? If it is nearly sorted, then insertion sort is definitely faster. In fact it runs in linear time in that case. Compared to selection sort, which is O(n^2). It really just depends on the array, but in general Insertion sort takes the cake.

$\endgroup$
  • 1
    $\begingroup$ I don't see how this answers the question. You are just summarizing how those algorithms work, but I don't think that's what the question was asking for. $\endgroup$ – D.W. Feb 27 '17 at 23:02
  • $\begingroup$ @D.W. It asked to explain each algorithm, first sentence, which I did. Then I compared the performance which answers his question of which one to use. $\endgroup$ – YungGun Feb 28 '17 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.