arcbjorn

thoughtbook

Wednesday, February 15, 2023

Sort an array

Leetcode 912 problem.

A function, given an array of integers nums, sort the array in ascending order and return it.

Go

Selection Sort

  • Time complexity: O(n2)O(n^{2}) - n is a length of an array
  • Auxiliary space: O(1)O(1) - constant amount of space
func sortArray(nums []int) []int {
    length := len(nums)

    // Simple Selection Sort
    for i := 0; i < length-1; i++ {
        index_min := i

        // compare current value with next values 1 by 1 and save new minimum index
        for j := i+1; j < length; j++ {
            if (nums[j] < nums[index_min]) {
                index_min = j
            }
        }

        old_value_min := nums[index_min]
        // set current value to minimum value index (swap)
        nums[index_min] = nums[i]
        // set minimum value to current position (since it's less)
        nums[i] = old_value_min
    }

    return nums
}

Bubble Sort

  • Time complexity: O(n2)O(n^{2}) - n is a length of an array
  • Auxiliary space: O(1)O(1) - constant amount of space
func sortArray(nums []int) []int {
    length := len(nums)
    
    for i :=0; i < length; i++ {
        // compare current index to each item
        for currentIdx := range nums {
            if length > currentIdx + 1 {
                // swap values positions if current value > next value
                if nums[currentIdx] > nums[currentIdx + 1] {
                    nums[currentIdx], nums[currentIdx+1] = nums[currentIdx+1], nums[currentIdx]
                }
            }
        }
    }

    return nums
}

Insertion Sort

  • Time complexity: O(n2)O(n^{2}) - n is a length of an array
  • Auxiliary space: O(1)O(1) - constant amount of space
func sortArray(items []int) []int {
    length := len(items)
    
    for i := 1; i < length; i++ {
        j := i

        // compare current item to each item before it
        for j > 0 {
            // swap values positions if previous value > current value
            if items[j-1] > items[j] {
                items[j-1], items[j] = items[j], items[j-1]
            }
            j--
        }
    }

    return items
}

Merge Sort

  • Time complexity: O(nlogn)O(n * log_n) - n is a length of an array
  • Auxiliary space: O(n)O(n) - n is a length of an array
func sortArray(slice []int) []int {
    length := len(slice)

    if length < 2 {
        return slice
    }

    midIndex := length / 2

    return Merge(sortArray(slice[:midIndex]), sortArray(slice[midIndex:]))
}

func Merge(left, right []int) []int {
    rightSliceLength := len(right)
    leftSliceLength := len(right)

    length, i, j := leftSliceLength + rightSliceLength, 0, 0
    // merged slice
    slice := make([]int, length, length)

    // first 2 cases are for arrays of different length

    for k := 0; k < length; k++ {
        // if i > left last index && j <= right last index, pick from right
        if i > leftSliceLength - 1 && j <= rightSliceLength - 1 {
            slice[k] = right[j]
            j++

        // if j > right last index && i <= left last index, pick from left
        } else if j > rightSliceLength - 1 && i <= leftSliceLength - 1 {
            slice[k] = left[i]
            i++

        // if left < right, pick left
        } else if left[i] < right[j] {
            slice[k] = left[i]
            i++
            
        // else pick right
        } else {
            slice[k] = right[j]
            j++
        }
    }

    return slice
}

Quick Sort

  • Time complexity: O(nlogn)O(n * log_n) - n is a length of an array
  • Auxiliary space: O(n)O(n) - n is a length of an array
func sortArray(nums []int) []int {
    quickSort(nums, 0, len(nums)-1)

    return nums
}

func quickSort(nums []int, left, right int) {
    // while there is a distance between left and right
    if left < right {
        // get new division point
        divisionIndex := divide(nums, left, right)

        // sort up to this division point
        quickSort(nums, left, divisionIndex - 1)
        // sort from this division point
        quickSort(nums, divisionIndex + 1, right)
    }
}

func divide(nums []int, left, right int) int {
    // starting from item with index 0
    divisionItem := nums[left]

    // while there is a distance between left and right
    for left < right {
        // if the right limiter point >= division point, decrement the right limit
        for left < right && nums[right] >= divisionItem {
            right--
        }

        // swap values for start and end
        nums[left], nums[right] = nums[right], nums[left]

        // if the start point <= division point, increment the left limit
        for left < right && nums[left] <= divisionItem {
            left++
        }

        // swap values for start and end
        nums[left], nums[right] = nums[right], nums[left]
    }
    return left
}

Counting Sort

  • Time complexity: O(n)O(n) - n is a length of an array of numbers
  • Auxiliary space: O(n)O(n) - n is a length of an array of numbers
func sortArray(nums []int) []int {
    maxNumber := nums[0]

    // iterate and compare to find max number in array
    i := 1
    for i < len(nums) {
        if nums[i] > maxNumber {
            maxNumber = nums[i]
        }

        i++
    }

    // index is a number value, length = the biggest number
    indices := make([]int, maxNumber + 1)

    i = 0
    for i < len(nums) {
        // index = number value
        // value is a frequency of the number in `nums` array
        indices[nums[i]]++

        i++
    }

    i = 1
    for i < len(indices) {
        // increase frequency of each number by adding frequency of previous number
        indices[i] += indices[i - 1]

        i++
    }

    // list of actual numbers
    sortedList := make([]int, len(nums))

    i = 0
    for i < len(nums) {
        // index of sortedList = value (frequency) of the actual number from indices array - 1
        // value of sortedList = actual number
        sortedList[indices[nums[i]] - 1] = nums[i]

        // decrease value of the frequency of current number in indices array
        indices[nums[i]]--

        i++
    }

    return sortedList
}
Creative Commons Licence