We are not going to go into advanced sorting like merge sort & quick sort here. I will try to explain some core concepts within sorting. Then I will show three types of sorting algorithms like Insertion, Selection and the famous Bubble-sort.
First of all, we need to understand how binary search works. For this purpose, we will use an array.
\(arr = [1, 2, 4, 5, 6, 7]\)
If we want to find the number 2 in this array, we can start looking at the middle of the array and determine if our number is equal to the current number, which in this case is 4... "It is not equal.". We have concluded that our element is less than 4, so now we change the last and middle values of our current array so that the last becomes the middle and the middle becomes the new high value divided by the first, resulting in
\(arr = [1, 2, 3]\)
And we do the whole thing again, and check if the middle value is equal to our number... It is. That means that we have found our number using binary search. This may seem arbitrary, but the binary search has a time complexity of Big O(log n). This means that finding 1 million sorted items requires 20 "checks" and 1 billion requires 29, 9. However, this means that binary search is a logarithmic action. 2, 4, 8, 16, 32...
It's important to remember that binary searches only work with sorted data. So sorting is quite crucial. Computers have very poor tunnel vision. Sorting an array-like.. ->
\(arr = [4, 3, 6, 1]\)
This would not be hard for a human, but for a computer, it's not so easy. The computer can only compare two values at a time. So we need to develop algorithms for the computer to be able to sort efficiently. In sorting you often find the term "divide & conquer".
What does "Divide & Conquer" mean?
Divide and Conquer means that we split the array into multiple arrays and sort the values separately. Click here if you wanna know more about "Divide and Conquer" algorithms like quick-sort and merge-sort.
array
Explanation & Code
In C# you create an array like this. Read the comments.
Array is the data-structure that will be used during bubble & selection sort.
function
Array Push
When you push an element into the array, it will take the next free spot. If we create an integer array with size 7. The array currently contains the numbers 1 and 2. So if we push number 4 onto the array. It would be placed at index 2, or = [1, 2, 4, x, x, x, x](x = empty).
function
Array Peak
This simple program will just print every element in the array.
function
Array Pop
When you pop an element from an array you remove it. The way to do that dynamically is to transfer all the items the user dosen't wanna delete to another array. This code will not be following that approach.
Let's say we have an array like this z = [0, 1, 2].
Lets say we wanted to remove index 1.
If we just set z[1] to 0, the array will look like this; z = [0, x, 2].
That's not correct we still have to move "2" to index pos 1.
algorithm
bubble-sort
Explanation & CSharp Code
"SCHMIDT: Now, Senator, you're here at Google and I like to think of the presidency as a job interview. Now, it's hard to get a job as president. And--I mean, you're going to do a great job. It's also hard to get a job at Google. We have questions and we ask our candidates questions. And this one is from Larry Schwimmer. What--you guys think I'm kidding, it's right here.[1] What is the most efficient way to sort a million 32-bit integers?OBAMA: Well...
SCHMIDT: Maybe--I'm sorry...
OBAMA: No, no, no, no. I think--I think the bubble sort would be the wrong way to go."
Bubble Sort is infamous for being a very slow sorting algortihm. Bubble Sort is a good sorting algorithm for beginners since it usally makes sense. Bubble Sort works in O(n²) which is really bad. So 4 elements would take 16 steps to bubble sort at worst case.
steps
\(1.\) Comparetwo values that are next to each other.\(2.\) If the left values is greater, swap them.
\(3.\) Move one index to the right.
code
algorithm
selection-sort
Explanation & CSharp Code
The difference between selection-sort and bubble-sort is the number of swapping operations needed during runtime.
swaps
\(1.\) Bubble-sort \(O(n^2)\)\(2.\) Selection-sort \(O(n)\)
The code displays this quite perfectly. bubble-sort swaps on the second for-loop. Check code below...
For loop ONE got executed 8 times, while For loop TWO got executed 64 times.
Which is \((8^2)\) which is \(O(n^2)\), this means that bubble-sort swaps on the second for loop which requires elements of x^2. Selection-sort on the other hand swaps on first for loop.
Which results in \((8)\) which is \(O(n)\).
Selection-sort requires the same amount of swaps as there are elements in the main array.
In our example for loop ONE was executed 8 times.
The diffrence between 8-64 executions is minimal in most cases but...
Let's say you had to pay 5$ for every memory swap. This would make selection-sort a way better option then bubble-sort. Check code below for algo explanation