Searching and Sorting an Array

Introduction

In this page, we will explore several different types of sorting algorithm, pseudocodes and Java programs of them, and their real life applications.

Linear / Sequential Search

We choose an element first and compare each element in order with the chosen one. For example, searching for a word in a paper dictionary or searching a person in the phonebook apply sequential search as we find the targeted element by starting from the first one and end when we found it.

set POSITION to 0
set FOUND to false
loop while (POSITION < LENGTH and NOT FOUND)
    if(numbers [position] quals searchitem) then
        set FOUND to true
    else
        set POSITION to POSITION + 1
end loop

Binary Search

Binary search is about “compare and cut.” It is very important to know that we are looking for a target from an already sorted list. We compare the target value with the middle element on the list first and cut off the half that is far large or far small to the target. Then we compare the target with the new middle in the remained half of the list and repeat this “compare and cut” process until we found the target. Its application is on already sorted arrays.



Bubble Sort

Bubble sort is to repeat comparing two elements from the first to the last or from the last back to the first. Bubble sort is used in programming TV remote to sort channels on the basis of longer viewing time.

Bubble Sorting Down

set firstUnsorted to 0
set SWAP to true
loop while (firstUnsorted < LENGTH - 1 and SWAP)
    set SWAP to false
    set INDEX to LENGTH - 1
    while (INDEX > firstUnsorted)
        if(DATA[INDEX] < DATA[INDEX-1])
            swap DATA[INDEX] and data[INDEX-1]
            set SWAP to true
        set INDEX to INDEX-1
    end loop
    set firstUnsorted to firstUnsorted +1
end loop



The “Down” method check the order from the last element to the first. The system compare data[5] and data[4] first, if data[5] < data[4], it will swap their position by creating a temp to store data[5], equating data[5] to data[4], and equating data[4] to temp. Then, it will compare data[4] and data[3], data[3] and data[2]…until it reaches data[0] because the second while loop will stop when index>=firstUnsorted. Then firstUnsorted will increase for 1, and the comparison except the last element in the array will start over. SWAP is used as a flag here, making the program more efficient. If there is no swap in the whole second while loop, it means that all elements are sorted in the correct order, so there is no need to further check the order. The SWAP boolean will remain false and the first while loop will not be carry on further.

Output



Bubble Sorting Up



The “Up” Bubble sort starts comparing from the first element to the last one. Algorithm is the same as “Down” bubble sort.

Selection Sort

set firstUnsorted  to 0
loop while (firstUnsorted < LENGTH)
    set indexOfSmallest = firstUnsorted
    set INDEX = firstUnsorted + 1
    loop while (INDEX <= LENGTH -1)
        if(DATA[INDEX] < DATA[indexOFSmallest])
            set indexOfSmallest to INDEX
        end if
        set INDEX to INDEX + 1
    end loop
    set temp = DATA[firstUnsorted]
    set DATA[firstUnsorted] = DATA[indexOfSaallest]
    set DATA[indexOfSmallest] = temp
    set firstUnsorted to firstUnsorted + 1
end loop     

1. Find the largest number
2. Put the largest number in the first place



We set the value of indexOfSmallest to be zero first and then loop the rest of the element to compare them will data[0]. Whenever an element is smaller than the value of current data[indexOfSmallest], it will replace this. Therefore, the program will find the smallest and put it to the data[0] position and start finding the second small value for data[1].

Selection sort is useful when certain program requires to output the numbers one by one from the largest to the smallest.

Output



Big O Notation

A standard that indicates the complexity of an algorithm.

O(n): one loop

O(n^2): one loop inside one loop

O(2n): two loops

Conclusion

By knowing different ways of sorting, I can choose the most efficient way to sort under different circumstances, for example, searching name in a phonebook (binary), sort TV channels based on viewing time (bubble), or output from the largest (selection), etc.

Citation

Kanungo, A. (2016). What are the uses of different sorting algorithms like bubble, selection, insertion, shell, merge, heap, quick, tree, radix, counting and bucket sort in real-life scenarios?. Quora. Retrieved 21 September 2017, from