Сортировка

Алгоритмы сортировки §

📂 Алгоритмы

Сортировка пузырьком (bubble sort) §

Время: О(n**2)

Используем вложенные циклы, внешний проходит по всему массиву (i), вложенный по его неотсортированной части (j). При обнаружении j-элемента меньшего, чем i-элемент, меняем значения местами. Таким образом, список будет отсортирован по возрастанию. Чтобы отсортировать по убыванию, поменять сравнение на >.

def sort_list(source_list: list) -> list:
    sorted_list = source_list[:]
 
    for i in range(len(sorted_list)):
        for j in range(i + 1, len(sorted_list)):
            if sorted_list[j] < sorted_list[i]:
                sorted_list[j], sorted_list[i] = sorted_list[i], sorted_list[j]
 
    return sorted_list
 
 
my_list = [9, 8, 7, 6, 5, 4, 3, 2, 1]
 
print(sort_list(source_list=my_list))

Сортировка выбором §

Время: О(n**2)

Находим максимальный элемент, перемещаем его в новый массив. Повторяем операцию среди оставшихся элементов, пока они не закончатся.

def find_index_of_smallest(array: list) -> int:
    smallest = array[0]
    smallest_index = 0
 
    for i in range(1, len(array)):
        if array[i] < smallest:
            smallest = array[i]
            smallest_index = i
 
    return smallest_index
 
 
def sort_list(source_list: list) -> list:
    sorted_array = []
    for i in range(len(source_list)):
        smallest_index = find_index_of_smallest(source_list)
        # Remove item from source_list, appending it to sorted array.
        sorted_array.append(source_list.pop(smallest_index))
    return sorted_array
 
 
my_list = [9, 8, 7, 6, 5, 4, 3, 2, 1]
 
print(sort_list(source_list=my_list))

Быстрая сортировка §

Время: O(n * logn)

Грокаем, стр. 85.

Является рекурсивным алгоритмом. Базовый случай – пустой массив, массив с одним элементом.

Используется стратегия “разделяй и властвуй”. Следовательно, массив должен разделяться до тех пор, пока мы не придём к базовому случаю.

Сначала в массиве выбирается элемент, который называется опорным. Это будет первый элемент массива (рекомендуется выбирать случайный элемент).

Затем находится элементы меньшие опорного, и большие опорного. Этот процесс называется разделением.

def quicksort(source_list: list) -> list:
    # Base case
    if len(source_list) < 2:
        return source_list
    # Recursive step
    else:
        pivot = source_list[0]
        less = [i for i in source_list[1:] if i <= pivot]
        greater = [i for i in source_list[1:] if i > pivot]
 
        return quicksort(less) + [pivot] + quicksort(greater)
 
 
my_list = [9, 8, 7, 6, 5, 4, 3, 2, 1]
 
print(quicksort(source_list=my_list))

// https://www.codewars.com/kata/5174a4c0f2769dd8b1000003/train/go
package kata
 
func SortNumbers(numbers []int) []int {
  if numbers == nil {
    return []int{}  
  }
  
  if len(numbers) < 2 {
    return numbers
  }
  
  pivot := numbers[0]
  var less []int
  for _, i := range numbers[1:] {
    if i <= pivot {
      less = append(less, i)
    }
  }
  
  var more []int
  for _, i := range numbers[1:] {
    if i > pivot {
      more = append(more, i)
    }
  }
  
  return append(append(SortNumbers(less), pivot), SortNumbers(more)...)
}

export function solution(nums: number[]): number[] {
  if (!nums.length) return []
  
  if (nums.length < 2) return nums;
  
  const pivot = nums[0];
  const less: number[] = [];
  const more: number[] = [];
  nums.slice(1).map((i) => {
    if (i <= pivot) less.push(i);
    else if (i > pivot) more.push(i);
  });
  
  return [...solution(less), pivot, ...solution(more)]
}

Ссылки §

• https://www.techinterviewhandbook.org/algorithms/sorting-searching/

---

📂 Алгоритмы | Последнее изменение: 07.02.2024 20:18