Algorithms: Sorting Flashcards
Different Sorting Algorithms?
Insertion Sort
Selection Sort
Insertion Sort: Overview
Starts at second item in list, compares the item to the item immediatly to it’s left to see if it is smaller than that item. if it is smaller, it swaps the two items, and moves to the next item, repeating the process untill the entire list is sorted.
Selection Sort: Overview
Starts at and identifies the first item in list as the minimum value, then compares that item to every other item, after itself, in the list, and resets the minimum value to the value that is the smallest, after which it swaps the minimum value with itself so that the first item in the list is the smallest item. Once the first item is sorted it moves on to the second item and repeats the process untill the whole list is sorted.
Quick sort: Overview
Quick sort follows Divide and Conquer algorithm. It is dividing elements in to smaller parts based on some condition and performing the sort operations on those divided smaller parts. Hence, it works well for large datasets. So, here are the steps how Quick sort works in simple words.
First select an element which is to be called as pivot element.
Next, compare all array elements with the selected pivot element and arrange them in such a way that, elements less than the pivot element are to it’s left and greater than pivot is to it’s right.
Finally, perform the same operations on left and right side elements to the pivot element.
Quick Sort: Steps
STEP 1: Determine pivot as middle element. So, 7 is the pivot element.
STEP 2: Start left and right pointers as first and last elements of the array respectively. So, left pointer is pointing to 5 at index 0 and right pointer is pointing to 9 at index 5.
STEP 3: Compare element at the left pointer with the pivot element. Since, 5 < 6 shift left pointer to the right to index 1.
STEP 4: Now, still 3 <6 so shift left pointer to one more index to the right. So now 7 > 6 stop incrementing the left pointer and now left pointer is at index 2.
STEP 5: Now, compare value at the right pointer with the pivot element. Since 9 > 6 move the right pointer to the left. Now as 2 < 6 stop moving the right pointer.
STEP 6: Swap both values present at left and right pointers with each other.
STEP 7: Move both pointers one more step.
STEP 8: Since 6 = 6, move pointers to one more step and stop as left pointer crosses the right pointer and return the index of the left pointer.
Quick Sort: Steps
[5,3,7,6,2,9]
STEP 1: Determine pivot as middle element. So, 7 is the pivot element.
STEP 2: Start left and right pointers as first and last elements of the array respectively. So, left pointer is pointing to 5 at index 0 and right pointer is pointing to 9 at index 5.
STEP 3: Compare element at the left pointer with the pivot element. Since, 5 < 6 shift left pointer to the right to index 1.
STEP 4: Now, still 3 <6 so shift left pointer to one more index to the right. So now 7 > 6 stop incrementing the left pointer and now left pointer is at index 2.
STEP 5: Now, compare value at the right pointer with the pivot element. Since 9 > 6 move the right pointer to the left. Now as 2 < 6 stop moving the right pointer.
STEP 6: Swap both values present at left and right pointers with each other.
STEP 7: Move both pointers one more step.
STEP 8: Since 6 = 6, move pointers to one more step and stop as left pointer crosses the right pointer and return the index of the left pointer.
