One of the most important things we should pay attention to when writing code is the time (time) and space (space) complexity of the code we write.. Although we do not pay attention to small-scale projects, we need to pay attention to these in projects consisting of thousands, tens of thousands, maybe even hundreds of thousands of lines of code.. There are some algorithms currently being used for this.. Binary Search, which we mentioned in one of our previous articles, is an example of these.. When searching for an element in a sorted array, we can directly compare all the elements of the array with the element we are looking for.. But in directories with too many elements, this will make our system quite difficult.. That’s why we use Binary Search. So how do we make a directory sorted? Sorting algorithms come to our aid in this regard..
Before we go over the examples, let’s define the directory we will sort through in Python.
arr = [22,54,11,2,87,63,102,41,10,66]
In this way 10 we have an elemented and unordered list. Now let’s sort this index with popular sorting algorithms.
Selection Sort :
Selection Sort is actually one click away from other sorting algorithms in terms of performance. even though it is weak, it helps us in difficult situations. This algorithm, which is very simple to implement, assumes that the first element of the array is the smallest element.. Then it compares this element with other elements one by one. If the element it is comparing is smaller, it takes it as the smallest value and now compares the other elements with it instead of the first element.. When it reaches the end of the array, it writes the smallest element to the beginning of the array.. Then do this 2. It starts from the element and finds the smallest value of 2. puts it in order and repeats this process until the last element of the array.. The encoding part of Selection Sort is as follows :
for i in range(len(arr)): enKucukIdx = i for j in range(i+1,len(arr)): if arr[j] < arr [enSmallIdx]: enSmallIdx = j arr[i],arr[enSmallIdx] = arr[enSmallIdx], arr[i]
Selection Sort time complexity :
- Best Case (En good case) : O(n²)
- Worst Case : O(n²)
- Average Case: O(n²)
Bubble Sort:
Bubble Sort, also known as bubble sorting algorithm. Perhaps the easiest to implement and grasp is the sorting algorithm. Bubble Sort compares the elements in our array binary by pair and swaps them out if the left element is greater than the right. Repeats this until the end of the list.
for i in range(len(arr)-1): for j in range(0,len(arr)-i-1): if arr[j] > arr[j+ 1]: arr[j], arr[j+1] = arr[j+1],arr[j]
As you can see, we can sort our index with a short code snippet. The time complexity of Bubble Sort is :
- Best Case : O(n)
- Worst Case : O(n²)
- Average Case : O(n²)
Insertion Sort :
Again, we are examining a sorting algorithm that is not very difficult to implement.. Insertion starts from the second element of the array and goes towards the end.. It keeps the element it is looking at at a value and compares it until it finds the smallest element from that element to the beginning of the array.. As seen in the example above, when the algorithm grabs an element, it compares and compares it to the left..
Many people sort their cards with the Insertion Sort logic in card games.
Insertion Sort coding is as follows:
for i in range(1,len(arr) ): value = arr[i] j = i-1 while(j>= 0 and value < arr[j]): arr[j+1] = arr[j] j -= 1 arr[j+1] = value
Time complexity of Insertion Sort :
- Best Case : O(n)
- Worst Case : O(n²)
- Average Case : O(n²)
Merge Sort:
A little complicated to implement compared to other sorting algorithms, but in terms of speed and memory used Merge Sort works with the Divide and Conquer approach, which is a more efficient algorithm than them.. Then it starts merging these small directories among themselves. When doing this merge, it also does the sorting with it.
def merge(left, right): if not len(left) or not len(right): return left or right result = [] i, j = 0, 0 while (len(result) < len(left) + len(right)): if left[i] < right[j]: result.append(sol[i]) i+= 1 else: result.append(right[ j]) j+= 1 if i == len(left) or j == len(right): result.extend(left[i:] or right[j:]) break return result def mergesort(arr): if len (arr) < 2: return arr middle = len(arr)//2 left = mergesort(arr[:mid]) right = mergesort(arr[middle:]) return merge(left, right)
Merge Sort’ un time complexity :
- Best Case : O(n*log n)
- Worst Case : O(n*log n)
- Average Case: O(n*log n)
Quick Sort:
Quick Sort aka Quick Sort also Split like Merge Sort and it works with the Conquer approach. The algorithm selects an element as the pivot value and sorts the elements around that value.
There are many different ways to select the pivot element in Quick Sort. The most used ones are:
- Selecting the first element as the pivot
- Selecting the last element as the pivot
- Selecting a random element as the pivot
- Selecting the median value as the pivot
<
Although Quick Sort was developed in 1959, it is 3 times faster than competitors such as Merge Sort.
In Quick Sort, the pivot is selected and the other values of the array are thrown to the right of the pivot if it is large, and to the left of the pivot if it is small.. Then the same process is applied to the 2 indexes on the right and left, and this continues until the number of elements of the checked array is 1.. After the shredding, the index becomes sorted while merging.
Let’s look at this example where the last element is always selected as the pivot value:
def fragmentation(arr,low,high): i = (low-1) pivot_value = arr[high] for j in range(low , high): if(arr[j] < pivot_value): i = i+1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[high] = arr[high],arr[i+1] return ( i+1 ) def quickSort(arr,low,high): if(low < high): pivot_value = shard( arr,low,high) quickSort(arr, low, pivot_value-1) quickSort(arr, pivot_value+1, high) quickSort(arr,0,len(arr)-1)
Quick Sort time complexity :
- Best Case: O(n*log n)
- Worst Case: O(n²)
- Average Case: O(n*log n)
These sorting algorithms, which allow us to keep the indexes in memory in order, generally work in these ways.. These 5 examples we have given are the most well-known ones, but you can check out all the other sorting algorithms here.