Sorting algorithms are methods of sorting an array (list) of data in to numeric order. There are various sorting methods and each has its advantage and disadvantage. Some algorithms work great for short lists and some are much better suited to large lists. When you try these sorting algorithms it is interesting to add a timer so you can see a comparison of time taken for different data sets.
BUBBLE SORT
ABOUT BUBBLE SORT
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO
<
>
The bubble sort is a simple sorting algorithm and you can think of it are a bubble repeatedly going through a list and sorting two items at a time until the entire list is sorted. The bubble will always have to pass the length of the list -1 times to ensure the entire list is sorted. Below is an illustration of a bubble sort, the list in the illustration has 6 numbers therefore 5 passes/loops are needed. You will also notice that during each pass the number of list items that the bubble will need to check is reduced by 1, this is because after the first pass the last number will always be sorted, the second pass the next to last will always be sorted and so on.
Whilst the bubble sort works fine with short lists it is not an efficient sort to use with long list. To make the sort slightly more efficient you could add a condition to end the sort if on any pass no swaps were made as this would mean the list was already sorted.
Adding a while loop to the bubble sort could make the sort very quick if the last part of the list is already sorted, this is because you can break the sort if no changes are needed, this works with the bubble sort because it passes through the list multiple times.
Extended version of the sort - showing how to break the loop if the list is already sorted. This is done by checking if any changes were needed on each complete pass of the list.
LISTLEN = LEN(VALUES) SWAP = TRUE loop while SWAP = TRUE SWAP = FALSE loop COUNTER from 0 to LISTLEN - 1 if VALUES[COUNTER] > VALUES[COUNTER + 1] then TEMPORARY = VALUES[COUNTER] VALUES[COUNTER] = VALUES[COUNTER + 1] VALUES[COUNTER + 1] = TEMPORARY SWAP = TRUE end if end loop end loop
MERGE SORT
ABOUT MERGE SORT
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO
<
>
Merge Sort is a sorting algorithm that follows the Divide and Conquer approach to sort a given list of elements. It divides the input list into two halves, recursively sorts the two halves, and then merges the sorted halves into a single sorted list.
The basic steps to perform a merge sort are:
Divide the unsorted list into n sublists, each containing one element (base case).
Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
The sets needed to perform a merge sort are:
Unsorted list - This is the input list that needs to be sorted.
Temporary arrays - These arrays are used for storing the sublists generated during the merge process.
Start and end indices - These indices are used to indicate the start and end positions of the sublists while dividing the unsorted list.
A merge function - This function is used to merge two sorted sublists into a single sorted list.
Recursion - The merge sort algorithm uses recursion to sort the sublists generated during the divide process.
This code first defines a merge() function that takes in an array and indices for the left, middle, and right sub-arrays, and merges the two sub-arrays into a single sorted array. The mergeSort() function then recursively divides the input array into two halves, calls itself on each half, and finally merges the two halves using the merge() function. The code generates a list of 1000 random integers, sorts it using Merge Sort, and prints the sorted list and the time taken to sort it.
This pseudocode defines a MERGE_SORT function that takes in an array VALUES, sorts it using the Merge Sort algorithm, and returns the sorted array. The function recursively divides the input array into two halves, calls itself on each half, and finally merges the two halves using the LINDEX and RINDEX variables to keep track of the indices in the left and right sub-arrays respectively. The LEFT and RIGHT variables represent the left and right sub-arrays of the input array. The LEN() function returns the length of an array or slice.
QUICK SORT
ABOUT QUICK SORT
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO
<
>
Quick Sort is a popular sorting algorithm that works by partitioning an array into two sub-arrays, one containing elements that are less than or equal to a pivot element and the other containing elements that are greater than the pivot. The pivot element is chosen at random or as the first, last, or middle element of the array. The main steps involved in Quick Sort are:
Choose a pivot element.
Partition the array into two sub-arrays, one with elements less than or equal to the pivot, and the other with elements greater than the pivot.
Recursively apply the above two steps to each of the sub-arrays until the entire array is sorted.
The sets needed to implement Quick Sort include the array to be sorted, the left and right indices of the sub-array being sorted, and the pivot element. The partitioning function also requires two pointers that traverse the sub-array being sorted from the left and right ends, respectively. Additionally, the partitioning function needs to swap elements in the sub-array to ensure that the elements less than or equal to the pivot are on the left and the elements greater than the pivot are on the right.
The partition() function implements the partitioning step in Quick Sort and returns the index of the pivot element. The quickSort() function recursively sorts the left and right sub-arrays of the input array. The left and right parameters in quickSort() represent the left and right indices of the sub-array being sorted.
The partition() function implements the partitioning step in Quick Sort and returns the index of the pivot element. The quickSort() function recursively sorts the left and right sub-arrays of the input array. The left and right parameters in quickSort() represent the left and right indices of the sub-array being sorted.
This non-recursive implementation of Quick Sort uses a stack to keep track of sub-arrays to be sorted. The STACK variable stores the indices of sub-arrays in the input array. The while loop continues until the stack is empty. In each iteration of the loop, the right and left indices of the next sub-array to be sorted are popped from the stack. The partitioning step is then performed on the sub-array, and the resulting left and right sub-arrays are pushed to the stack if they have more than one element. This process continues until the stack is empty, resulting in the entire array being sorted.
INSERTION SORT
ABOUT INSERTION SORT
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO
<
>
Insertion Sort is a simple sorting algorithm that works by dividing an input array into two parts, one sorted and the other unsorted. The algorithm then iterates over the unsorted part of the array, taking one element at a time and inserting it into its correct position in the sorted part of the array.
The main steps involved in Insertion Sort are:
Initialise a sorted section with the first element of the array.
Iterate over the unsorted section of the array.
For each element in the unsorted section, compare it with the elements in the sorted section and find its correct position.
Insert the element into its correct position in the sorted section.
Repeat steps 2-4 until the entire array is sorted.
Insertion Sorts can be implemented in different ways, such as using nested loops or using a recursive approach. The most common implementation uses nested loops, where the outer loop iterates over the unsorted section of the array, and the inner loop iterates over the sorted section to find the correct position to insert the element. The inner loop stops when it finds an element that is less than or equal to the current element, or when it reaches the beginning of the array.
The insertion sort below also records the time taken to sort, in this example a list of 1000 numbers has been sorted.
The insertion Sort function implements the Insertion Sort algorithm. The n variable stores the length of the input array. The for loop iterates over the unsorted section of the array. The while loop finds the correct position for the current element in the sorted section of the array. Finally, the main function generates a random list, sorts it using Insertion Sort, and prints the sorted list and the time taken to sort the list.
In this pseudocode, the INSERTION_SORT function implements the Insertion Sort algorithm using a non-recursive approach. The for loop iterates over the unsorted section of the input array, and the while loop finds the correct position for the current element in the sorted section of the array. The KEY variable stores the value of the current element being sorted, and the J variable keeps track of the position where the KEY element should be inserted. The VALUES array stores the input array to be sorted. The Len function returns the length of an array.
SELECTION SORT
ABOUT SELECTION SORT
IN PYTHON
IN JAVA
PSEUDOCODE
VIDEO
<
>
The selection sort works by finding the smallest item in the list and moving it to the first unsorted position in the list. The list starts to get sorted from the left and each pass over the entire list is smaller each time as the list gets sorted from left to right.
1: SET: Make the first item in the list the current smallest - index 0 of the list 2: SEARCH: Iterate through the list and if any item is smaller than the current smallest then make that the new current smallest. 3: SWAP: After the smallest item in the list is found swap the first unsorted number for the smallest - index 0 swaps with the smallest item on the first pass 4: INCREMENT: The first item in the list is already sorted so index 0 can now be ignored - index 1 becomes the new smallest. 5: REPEAT: Continue to loop until the list is sorted. Loop length of the list - 1 times.
Unlike the bubble sort, if no swap was needed on any particular pass the selection sort still needs to continue to iterate until the length of the list - 1 iterations are complete.
This code could be streamlined as can be seen below.
In this pseudocode, the SELECTION_SORT function implements the Selection Sort algorithm. The for loop iterates over the unsorted section of the input array. The MIN_INDEX variable stores the index of the minimum element in the unsorted section of the array, and the for loop inside the SELECTION_SORT function finds the index of the minimum element in the unsorted section of the array. The VALUES array stores the input array to be sorted, and the Len function returns the length of an array. The TEMP variable is used to swap the minimum element with the first element in the unsorted section of the array.
OTHER GOOD RESOURCES FOR THIS SECTION
Tutorials Point Great explanations and samples of various data structures
