Sort algorithms

10 December 2020

Bubble sort

The algorithm consists of repeated passes over the array being sorted.
For each pass, the elements are sequentially compared pairwise and, if the order in the pair is incorrect, a permutation of the elements is performed.
Algorithmic complexity is quadratic O(n²).

Go example

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   testDataLen := len(testData)
   var tmp int

   for i := 0; i < testDataLen; i++ {
      for j := 1; j < testDataLen; j++ {
         if testData[j-1] > testData[j] {
            tmp = testData[j-1]
            testData[j-1] = testData[j]
            testData[j] = tmp
         }
      }
   }

   fmt.Println(testData) // [-5 1 2 3 7 8 9]
}

PHP example

$testArray = [7, 2, -5, 3, 1, 9, 8];

$len = count($testArray);
for ($i = 0; $i < $len; $i++) {
    for ($j = $i + 1; $j < ($len); $j++) {
        if ($testArray[$i] > $testArray[$j]) {
            $tmp = $testArray[$j];
            $testArray[$j] = $testArray[$i];
            $testArray[$i] = $tmp;
        }
    }
}

echo implode(", ", $testArray) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Sort by inserts

We conditionally divide the array into 2 areas - sorted values on the left and unsorted values on the right.
The elements of the unsorted area are sequentially taken and inserted in the right place among the sorted ones.
Algorithmic complexity is quadratic O(n²).

Go example

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   testDataLen := len(testData)

   for i := 1; i < testDataLen; i++ {
      v := testData[i]
      idx := i

      for j := i - 1; j >= 0; j-- {
         if testData[j] > v {
            idx = j
         }
      }

      // Delete
      testData = append(testData[:i], testData[i+1:]...)

      // Insert
      testData = append(testData[:idx+1], testData[idx:]...)
      testData[idx] = v
   }

   fmt.Println(testData) // [-5 1 2 3 7 8 9]
}

PHP example

$testArray = [7, 2, -5, 3, 1, 9, 8];

$len = count($testArray);
for ($i = 1; $i < $len; $i++) {
    $v = $testArray[$i];
    $idx = null;

    for ($j = $i - 1; $j >= 0; $j--) {
        if ($testArray[$j] > $v) {
            $idx = $j;
        }
    }

    if ($idx === null) {
        $idx = $i;
    }

    // Delete
    unset($testArray[$i]);
    $testArray = array_values($testArray);

    // Insert
    $testArray = array_merge(
        array_slice($testArray, 0, $idx),
        [$v],
        array_slice($testArray, $idx)
    );
}

echo implode(", ", $testArray) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Merge sort

First, we recursively split the initial array into 2 parts until the array size reaches 1. Each of the resulting parts is sorted separately. Then we merge the sorted arrays into one.
Algorithmic complexity is linear-logarithmic O(n log n).

PHP example

function mergeSort(array $arr): array {
    $count = count($arr);

    if ($count <= 1) {
        return $arr;
    }

    $left  = array_slice($arr, 0, (int) ($count / 2));
    $right = array_slice($arr, (int) ($count / 2));

    // Recursive call
    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            array_push($result, array_shift($left));
        } else {
            array_push($result, array_shift($right));
        }
    }

    array_splice($result, count($result), 0, $left);
    array_splice($result, count($result), 0, $right);

    return $result;
}

$testArray = [7, 2, -5, 3, 1, 9, 8];

echo implode(", ", mergeSort($testArray)) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Go example

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}

   fmt.Println(mergeSort(testData)) // [-5 1 2 3 7 8 9]
}

func mergeSort(data []int) []int {
   length := len(data)

   if length <= 1 {
      return data
   }

   mid := length / 2

   // Recursive call
   return merge(mergeSort(data[:mid]), mergeSort(data[mid:]))
}

func merge(left []int, right []int) []int {
   var res []int

   for len(left) > 0 && len(right) > 0 {
      if left[0] < right[0] {
         res = append(res, left[0])
         left = left[1:]
      } else {
         res = append(res, right[0])
         right = right[1:]
      }
   }

   if len(left) > 0 {
      res = append(res, left...)
   }

   if len(right) > 0 {
      res = append(res, right...)
   }

   return res
}

Pyramidal sorting (heap sorting)

We use a binary sorting tree (binary heap, pyramid). It must satisfy the following conditions:
- the value at any vertex is not less than the values of the descendants;
- the depth of all leaves differs by no more than 1;
- the last layer is filled from left to right.
Algorithm:
- form the pyramid with the largest value at the root of the heap;
- change the last and the first elements of the heap;
- remove the last element of the heap (at the moment it is the largest, we put it aside);
- sort the obtained heap;
- repeat the above steps until the heap size > 1.

Algorithmic complexity is linear-logarithmic O(n log n).

PHP example

function heapSort(array $data): array {
    $len = count($data);

    for ($i = $len / (2 - 1); $i >= 0; $i--) {
        $data = heapify($data, $len, $i);
    }

    for ($i = $len-1; $i >= 0; $i--) {
        $temp = $data[0];
        $data[0] = $data[$i];
        $data[$i] = $temp;

        $data = heapify($data, $i, 0);
    }

    return $data;
}

function heapify(array $data, int $n, int $i): array {
    $largest = $i;
    $leftIndex = 2*$i + 1;
    $rightIndex = 2*$i + 2;

    if ($leftIndex < $n && $data[$leftIndex] > $data[$largest]) {
        $largest = $leftIndex;
    }

    if ($rightIndex < $n && $data[$rightIndex] > $data[$largest]) {
        $largest = $rightIndex;
    }

    if ($largest != $i) {
        $swap = $data[$i];
        $data[$i] = $data[$largest];
        $data[$largest] = $swap;

        $data = heapify($data, $n, $largest);
    }

    return $data;
}

$testArray = [7, 2, -5, 3, 1, 9, 8];

echo implode(", ", heapSort($testArray)) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Go example

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   fmt.Println(heapSort(testData)) // [-5 1 2 3 7 8 9]
}

func heapSort(data []int) []int {
   data = buildMaxHeap(data)
   fmt.Printf("Heap: %v\n", data) // Heap: [9 3 8 2 1 -5 7]
   
   size := len(data)
   for i := size - 1; i >= 1; i-- {
      data[0], data[i] = data[i], data[0]
      size--
      heapify(data[:size], 0)
   }
   return data
}

func buildMaxHeap(data []int) []int {
   for i := len(data)/2 - 1; i >= 0; i-- {
      data = heapify(data, i)
   }

   return data
}

func heapify(data []int, index int) []int {
   leftIndex := getLeftIndex(index) + 1
   rightIndex := getRightIndex(index) + 1
   var largest int

   if leftIndex < len(data) && leftIndex >= 0 && data[leftIndex] > data[index] {
      largest = leftIndex
   } else {
      largest = index
   }

   if rightIndex < len(data) && rightIndex >= 0 && data[rightIndex] > data[largest] {
      largest = rightIndex
   }

   if largest != index {
      data[index], data[largest] = data[largest], data[index]
      data = heapify(data, largest)
   }

   return data
}

func getLeftIndex(i int) int {
   return 2 * i
}

func getRightIndex(i int) int {
   return 2*i + 1
}

Quick sort

First select the reference element. Then we compare the elements with the reference element and place the smaller ones before it, the rest after it. Recursively repeat the actions for the left and right parts (we apply recursion until the size of the part becomes <= 1).
Algorithmic complexity is linear-logarithmic O(n log n).

PHP example

function quickSort(array $data) {
    $count = count($data);
    if ($count <= 1) {
        return $data;
    }

    $mainElem = $data[0]; // Take the first element as a reference
    $left = [];
    $right = [];

    for ($i = 1; $i < $count; $i++) {
        if ($data[$i] < $mainElem) {
            $left[] = $data[$i];
        } else {
            $right[] = $data[$i];
        }
    }

    // Recursive calls
    $left = quickSort($left); 
    $right = quickSort($right);

    return array_merge($left, array($mainElem), $right);
}

$testArray = [7, 2, -5, 3, 1, 9, 8];

echo implode(", ", quickSort($testArray)) . PHP_EOL; // -5, 1, 2, 3, 7, 8, 9

Go example

package main

import "fmt"

func main() {
   testData := []int{7, 2, -5, 3, 1, 9, 8}
   fmt.Println(quickSort(testData)) // [-5 1 2 3 7 8 9]
}

func quickSort(data []int) []int {
   dataLen := len(data)
   if dataLen < 2 {
      return data
   }

   var left, right []int
   mainElem := data[0]

   for i := 1; i < dataLen; i++ {
      if data[i] < mainElem {
         left = append(left, data[i])
      } else {
         right = append(right, data[i])
      }
   }

   left = quickSort(left)
   right = quickSort(right)

   left = append(left, mainElem)
   return append(left, right...)
}

Sources:
https://en.wikipedia.org/wiki/Bubble_sort
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort
http://php-zametki.ru/php-nachinayushhim/136-php-sortirovka.html
https://en.wikipedia.org/wiki/Heapsort
https://en.wikipedia.org/wiki/Quicksort

Article
Sort algorithms

Sort algorithms

Bubble sort

Sort by inserts

Merge sort

Pyramidal sorting (heap sorting)

Quick sort

Recent articles

Tags

ArticleSort algorithms

Sort algorithms

Bubble sort

Sort by inserts

Merge sort

Pyramidal sorting (heap sorting)

Quick sort

Recent articles

Tags

Article
Sort algorithms