Create FREE 'HowTo' Videos with MyGuide

Sorting II



Pass Quiz and Get a Badge of Learning



Content "filtered", Please subscribe for FULL access.


Chapter 12 : Sorting II


Radix Sort arrow_upward


  • Sorts integers by comparing individual digits sharing the same significant position.
  • A positional notation is required.
  • To sort an array of two-digit numbers, the algorithm makes two sorting passes through the array.
    • In the first pass, the elements of the array are sorted by the least significant decimal digit.
    • In the second pass, the elements of the array are sorted by the most significant decimal digit.
  • The second pass is done in such a way that it does not destroy the effect of the first pass.

  • Radix Sort Algorithm arrow_upward


    Step 1

  • Look at the rightmost digit.
  • Step 2

  • Assign the full number to that digit’s index.
  • Step 3

  • Look at the next digit to the   left from the current sorted array, if there is no digit, pad a 0.
  • Step 4

  • REPEAT STEP 3 UNTIL all numbers have been sorted.

  • Example:

  • Step 0
    • Original, unsorted list

  • Step 1
    • Sorting by least significant digit (1st place) gives.

    • Notice that we keep 802 before 2, because 802 occurred before 2 in the original list
    • Similarly, for pairs 170 & 90 and 45 & 75.
  • Step 2
    • Sorting by next digit (10th place) gives.

  • Step 3
    • Sorting by most significant digit(100th place) gives sorted list.

    Note:

  • Each of the above steps requires just a single pass over the data.
  • Each item can be placed in its correct bucket without having to be compared with other items.

  • Quick Sort arrow_upward


  • Quick sort is also known as "partition-exchange“ sort.
  • Rearranges array into two parts:
    • Left part ≤ pivot value
    • Right part > pivot value
  • Average case:
    • O(n log n) Comparisons to sort n items.
  • Worst case:
    • O(n2 ) Comparisons to sort n items.

    Quick Sort Algorithm arrow_upward


  • Quick Sort employs a divide and conquer strategy to divide a list into two sub-lists.
  • The algorithm is as follows:
    • Pick an element, called a Pivot, from the list.
    • Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.
    • After this partitioning, the pivot is in its final position.
    • This is called the Partition Operation.
    • Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

    Heap Sort arrow_upward


  • A Heap is a data structure.
  • Heap sort is a sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a Heap.
  • Heap Sort is an in-place sorting algorithm so it is memory efficient.

  • Complexity:

    O(nlog(n)) for n items.


    Heap Sort Algorithm arrow_upward


    Step1

    Build Heap- O(n)

  • Build a complete binary tree taking n items as input.
  • Ensure the binary tree satisfies the Heap Order property.
  • Step2

    Perform n deleteMax operations- O(log(n))

  • Delete the maximum element in the heap – which is the root node, and place this element at the end of the sorted array.

  • Example of Heap Sort arrow_upward


  • Given an array of 6 elements:
  •     15, 19, 10, 7, 17, 16,

  • Sort it in ascending order using heap sort.

  • Steps:

  • Consider the values of the elements as priorities and build the heap tree.
  • Start deleteMin operations, storing each deleted element at the end of the heap array.
  • After performing step 2, the order of the elements will be opposite to the order in the heap tree.
  • Hence, if we want the elements to be sorted in ascending order, we need to build the heap tree in descending order - the greatest element will have the highest priority.
  • Note that we use only one array , treating its parts differently:
    • When building the heap tree, part of the array will be considered as the heap, and the rest part - the original array.
    • When sorting, part of the array will be the heap, and the rest part - the sorted array.
    • This will be indicated by colors: white for the original array, blue for the heap and red for the sorted array.
    • Here is the array: 15, 19, 10, 7, 17, 6

    Building the heap tree:

  • The array represented as a tree, complete but not ordered:
  • Start with the rightmost node at height 1 - the node at position 3 = Size/2.
    It has one greater child and has to be percolated down:
  • After processing array[3] the situation is:
  • Next comes array[2]. Its children are smaller, so no percolation is needed.
  • The last node to be processed is array[1]. Its left child is the greater of the children.
  • The item at array[1] has to be percolated down to the left, swapped with array[2].
  • As a result the situation is:
  • The children of array[2] are greater, and item 15 has to be moved down further, swapped with array[5].
  • Now the tree is ordered, and the binary heap is built.
  • Sorting - performing deleteMax operations:

    Delete the top element 19.

    1. Store 19 in a temporary place. A hole is created at the top.

    2. Swap 19 with the last element of the heap.

    • As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
    •  Instead it becomes a cell from the sorted array.

    3. Percolate down the hole.

    4. Percolate once more (10 is less that 15, so it cannot be inserted in the previous hole).

  • Now 10 can be inserted in the hole.
  • 2. DeleteMax the top element 17:

    1. Store 17 in a temporary place. A hole is created at the top.

    2. Swap 17 with the last element of the heap.

    • As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
    • Instead it becomes a cell from the sorted array.

    3. The element 10 is less than the children of the hole, and we percolate the hole down:

    4. Insert 10 in the hole.

    DeleteMax 16:

    1. Store 16 in a temporary place. A hole is created at the top.

    2. Swap 16 with the last element of the heap.

    • As 7 will be adjusted in the heap, its cell will no longer be a part of the heap.
    • Instead it becomes a cell from the sorted array.

    3. Percolate the hole down (7 cannot be inserted there - it is less than the children of the hole).

    4. Insert 7 in the hole.

    DeleteMax the top element 15:

    1. Store 15 in a temporary location. A hole is created.

    2. Swap 15 with the last element of the heap.

    • As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
    • Instead it becomes a position from the sorted array.

    3. Store 10 in the hole (10 is greater than the children of the hole).

    DeleteMax the top element 10.

    1. Remove 10 from the heap and store it into a temporary location.

    2. Swap 10 with the last element of the heap.

    • As 7 will be adjusted in the heap, its cell will no longer be a part of the heap.
    •  Instead it becomes a cell from the sorted array.

    3. Store 7 in the hole (as the only remaining element in the heap.

    • 7 is the last element from the heap, so now the array is sorted.

    Thank You from Kimavi arrow_upward


  • Please email us at Admin@Kimavi.com and help us improve this tutorial.


  • Mark as Complete => Receive a Certificate in Data-Structure


    Kimavi Logo

    Terms and conditions, privacy and cookie policy | Facebook | YouTube | TheCodex.Me | Email Kimavi


    Kimavi - A Video Learning Library { Learning is Earning }

    Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only $10 a month



    All videos on this site created using MyGuide.

    Create FREE HowTo videos with MyGuide.