Bubble sort is one of the simplest sorting algorithms. The two adjacent elements of an array are checked and swapped if they are in wrong order and this process is repeated until we get a sorted array.

The steps of performing a bubble sort are:

• Compare the first and the second element of the array and swap them if they are in wrong order.
• Compare the second and the third element of the array and swap them if they are in wrong order.
• Proceed till the last element of the array in a similar fashion.
• Repeat all of the above steps until the array is sorted.

Video Tutorial for Shell sort [Not mine but explains very well]

Pros and Cons of Bubble Sort

Bubble sort, as such serves no benefit from the efficiency's point of view. Yet, it is taught in computer science courses, just for exploration of sorting techniques.

Analysis of Bubble Sort

• Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes.
• Bubble sort is both stable and adaptive.
• In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data.
• It can be practical if the input is usually in sort order but may occasionally have some out-of-order elements nearly in position.
• Bubble sort should be avoided in the case of large collections.
• It will not be efficient in the case of a reverse-ordered collection.
• NOBODY USES BUBBLE SORT

Insertion Sort

Kotlin Bubble Sort explanation :

• First of all, lets consider that given array is not sorter so that swaps are possible. And loop till there are no swaps or till the swap variable becomes false.

var swap = true
while(swap){

• Now we have to start to compare the element at index 0 with element at index at 1, so when we write something like this we got to stop iterating before the last index as when we use lastindex+1 index goes out of bounds.
  
  We would be able to compare the last element with previous one when we are writing last but one +1 -> last index

for(i in 0 until arr.size-1){

• Now compare the element at index with index+1, if element at index is bigger than element at index+1, then swap the elements
  
  Also set the Swap to be true.

if(arr[i] > arr[i+1]){
	val temp = arr[i]
	arr[i] = arr[i+1]
	arr[i + 1] = temp

	swap = true
}

fun bubbleSort(arr:IntArray):IntArray{
    var swap = true
    while(swap){
        swap = false
        for(i in 0 until arr.size-1){
            if(arr[i] > arr[i+1]){
                val temp = arr[i]
                arr[i] = arr[i+1]
                arr[i + 1] = temp

                swap = true
            }
        }
    }
    return arr
}

fun main(args: Array<String>) {
    val list = bubbleSort(intArrayOf(2,15,1,8,4))
    for (k in list) print("$k ")
}

Selection Sort

Recommended Reading

• Shell Sort
• Bubble Sort
• Cycle Sort
• Kotlin Basics
• Returning function from function
• Type inference
• Operators in Kotlin
• Write Properties File
• Koltin Annotations
• lambda accepting lambda
• Any & Unit & Nothing
• Logical Operators
• Excel Files
• File Operations