Intro to Sorting - Getting Started / Basic Algorithms

[algo.monster]

https://algo.monster/problems/sorting_intro

[Kalyan]

I would have appreciated if this page includes discussion of median of 3 partition quicksort, counting sort, radix sort & bucket sorting algorithms. If I am right, logic based on these come across very often in interviews…

[am1]

Hey, from my experience, algorithms like median of 3 quicksort is quite academic. I wouldn’t expect you to know that. The interview is more about applying relatively simple algorithms to solve problems (and coding them bug-free) rather than testing your raw knowledge.

[Waldo]

I’d like to see the implementations written in Javascript. My python knowledge is really basic and I find myself scratching my head a bit sometimes. Would it be possible to have these in Javascript or could you tell me if there’s a tool that can translate python to javascript?

[Titan]

Converting the mergeSort solution into a JS implementation proved to be quite difficult. May be useful to publish an explanation on the ideal algorithm for this language, as mentioned by Waldo.

[Alice]

Just to make sure my understanding is correct, in this case we’re setting the pivot to be value at the end of the array, so we don’t need this line at the end of sort_list_interval:
sort_list_interval(unsorted_list, start_ptr + 1, end)

But in general if we set the pivot to any other value this line above would be needed, right?

[Nick1]

Hi There!
I don’t see any output when I try to debug my C++ code with printing. For e.g. cout <<" Checking!" also doesn’t get printed on output screen!". It is really frustrating. It could be something silly from my end but not finding it intuitive to resolve this quickly. Any idea why cout not showing anything ? How do I debug my code? Request to reply asap.

[am1]

hmm, can you share your code? std::cout should work

[aka38]

“On the other hand, because the number of swaps between elements is very small (O(n)), it is good for sorting when the swapping speed is very slow.”

In the above line selection sort was not mentioned.

[Chris]

Basic insertion sort in JavaScript below. It took a while to figure out. Figuring out Merge Sort (in JS) and anything else advanced is feeling pretty overwhelming. Anyways good luck

function sortList(unsortedList){
for(i=0; i < unsortedList.length; i++){
let current = i;
while(current > 0 && unsortedList[current] < unsortedList[current - 1]){
let temp = unsortedList[current];
unsortedList[current] = unsortedList[current - 1];
unsortedList[current - 1] = temp;
current-=1;
}
}
return unsortedList;
}

[0xace]

In rust

Selection sort:
fn selection_sort(){
let mut b=vec![10,92,23,84,15];
let len = b.len();
for i in 0…len{
let mut min = i;
for j in i…b.len(){
if b[j] > b[min]{
min = j;
}

    }
    b.swap(i, min);
}
println!("selection {:?}",b)

}

[kajusa]

I think the following statement for Selection sort is wrong:

“This algorithm is not stable because an earlier element can jump after an element of the same value during a swap.”

Regardless of the programming language, we always use the “less than” comparison to find the minimum value in the array. For example, in Python:
if unsorted_list[j] < unsorted_list[min_index]

Or am I missing something?

[Ryan]

Hey Kajusa,
I will use ’ and ‘’ to differentiate between numbers with same value so we can see where they end up.
Consider the list [2’, 2’‘, 1]. Selection sort will find min_idx as 2, then swap 2’ and 1, making the list [1, 2’‘, 2’] after first pass through.
Then, the algorithm will continue going through the list and nothing will swap as it is already sorted.

[fulltime]

Would be nice to see a JavaScript implementation of Merge Sort

[Kareem]

I don’t understand this statement, “Note that during each pass, the largest element will always “float” to the top, like a bubble. Therefore, each pass, we only need to consider the interval excluding the last element of the previous interval.” Can someone explain?

[Daphne]

I think the description of merge sort could be clearer by stating it is a recursive algorithm which will continuously split itself in half until it has only 1 element. In my opinion, it is kind of odd to see the visual splitting the lists, but the written portion does not really mention the continuously splitting.

[Kirat]

Hi Kareem,
What they mean is that the largest element is always pushed backwards. You can see in line 8,9 of the python solution the swap continues until the element is followed by a larger value. That’s the “floating” action they mention. The interval is then shrunk since the end of the previous interval is now sorted. It’s a bit confusing as they actually reverse the range in the main loop which I initially missed myself.

[Straylight]

How to specify expected output for custom test cases?
My custom inputs are marked as wrong with blank expected output field.

[Vonkoff]

function insertionSortOther(arr) {
for (let i = 0; i < arr.length; i++) {
let curr = i;
for (let j = i; j > 0; j–) {
if (arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
} else {
break;
}
}
while (curr > 0 && arr[curr] < arr[curr - 1]) {
// const temp = arr[curr];
// arr[curr] = arr[i];
// arr[i] = temp;
[arr[curr], arr[i]] = [arr[i], arr[curr]];
i–;
}
}

return arr;
}

The following Javascript code for InsertionSort is faster. Replacing out the while loop with a for loop is better.

Below are my results using first InsertionSort with while and then instead with a For loop

insertionSort([1, 4, 2, 8, 345, 20]);
[ 1, 2, 4, 8, 20, 345 ]
default: 3.174ms

insertionSortOther([1, 4, 2, 8, 345, 20]);
[ 1, 2, 4, 8, 20, 345 ]
default: 0.198ms

[raj]

For selection sort, i think for the inner loop can start with i+1 the index:

def selection_sort(unsorted_list):
n = len(unsorted_list)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if unsorted_list[j] < unsorted_list[min_idx]:
min_idx = j
unsorted_list[i],unsorted_list[min_idx] = unsorted_list[min_idx],unsorted_list[i]
return unsorted_list