Some basic sort algorithms. Is Quick Sort the fastest sort algorithm?

Tram Ho

I. Introduction.

  • A practical problem is that you need to manage a class where the list of names or grades of the students are arranged in no particular order which makes it very difficult to manage so the problem is going to be The boss will make it easier for us to manage something.
  • Sorting is one of the most common practical problems in programming, it helps us to sort a list or an array in a certain order (usually ascending or descending).

II. Some common sort algorithms.

1. Bubble sort algorithm (Bubble Sort)

  • Idea: Constantly swapping adjacent elements if they are in the wrong order until the sequence is sorted.
  • Illustration

  • Code:

  • Analyze the problem
    • Suppose you need to arrange the sequence 5 3 2 7 in ascending order.

    loop 1:

    [ 5 3 2 7] -> [ 3 5 2 7], comparing 5 and 3 finds 3 smaller than 5 -> swapping 3 and 5.

    [3 5 2 7] -> [3 2 5 7], comparing 5 and 2 finds 2 less than 5 -> swapping 2 and 5.

    [3 2 5 7 ] -> [3 2 5 7 ], 5 <7 true -> nothing has changed

    -> end loop 1 we get [3 2 5 7]

    loop 2:

    [ 3 2 5 7] -> [ 2 3 5 7], comparing 3 and 2 finds 2 smaller than 3 -> swapping 2 and 3.

    [2 3 5 7] -> [2 3 5 7]], 3 <5 right -> nothing has changed.

    [2 3 5 7 ] -> [2 3 5 7 ], 5 <7 true -> nothing has changed.

    Here we get the sorted range but the algorithm has not stopped there but it continues to iterate.

    loop 3:

    [ 2 3 5 7] -> [ 2 3 5 7]

    [2 3 5 7] -> [2 3 5 7]

    [2 3 5 7 ] -> [2 3 5 7 ]

  • Algorithm complexity:

    Best case: O (n)

    Worst case: O (n * n)

2. Selection algorithm

  • The idea: Select the smallest (or largest) word in the sequence of n parts, bringing this word to the first position of the sequence and no longer care about this element. Continue to search for the smallest (or largest) element from the second position to the nth position in the n-1 sequence, bringing the word to the second position. Repeat until the sequence has only one element left.
  • Illustration

  • Code:

  • Analyze the problem
    • Suppose you need to arrange the sequence 5 7 3 2 in ascending order.

    Loop 1:

    [ 5 7 3 2 ] -> [ 2 7 3 5], finding 2 is the smallest number we change 2 to 5

    -> end loop 1 we get [2 7 3 5]

    Loop 2:

    [2 7 3 5 ] -> [2 3 7 5], find 3 which is the smallest number in the 2-n range from 3 to 7

    -> end loop 2 we get [2 3 7 5]

    Loop 3:

    [2 3 7 5 ] -> [2 3 5 7], find 5 which is the smallest number in the sequence from 3-n we swap places 5 for 7

    -> end of loop 3 we get [2 3 5 7]

    Loop 3 is also the last loop because the sequence has only 1 element, n is definitely the largest, so we have obtained an ascending sequence with the sorting algorithm.

  • Algorithm complexity:

    Best case: O (n * n)

    Worst case: O (n * n)

3. Quick sort algorithm (Quick Sort)

  • The idea: Quick sort is a division algorithm to value it to select an element in the array to make a marker. The algorithm will divide the array into sub-arrays according to the point you have selected. There are many ways to choose different points:

  • Illustration

  • Code:

  • Analyze the problem

  • Algorithm complexity

    Best case: O (nlog (n))

    Worst case: O (n * n)

So is the quick sort algorithm the fastest one?

The quick sort algorithm is not the fastest sort algorithm, depending on the input case, the algorithm will have different complexity, in the case of the worst possible input for quick sort The trash will be O (n * n) equal to other sort algorithms so it is not considered the fastest sort algorithm. Therefore, based on different problems, programmers need to choose different algorithms so that the problem is handled optimally.

III. Conclude

Sorting algorithm is a very common algorithm used in computer science. It helps us optimize the arrangement of an object, a list …

Therefore, it can not be denied the importance of the arrangement algorithm in the actual problems that programmers need to solve.

In addition to the above sorting algorithms, there are many other sorting algorithms that are extremely useful for programming of the developers.

IV. Refer

https://www.geeksforgeeks.org/quick-sort/

Share the news now

Source : Viblo