[アルゴリズム]ソート要約

1.ソート

sortは、特定の基準に基づいてデータをリストします.
通常、状況や条件に応じて、適切なアルゴリズムを使用するのは式のようです.

データが少ない場合は

データ量は大きいが、特定の範囲に限られている.

データがソートに近づいた場合、

1-1. ソケットの選択

「未処理のデータ」で、最小のデータを先頭に移動するアルゴリズムを選択します.
時間複雑度は等差数列式によりO(n^2)となる.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
  min_index = i
  for j in range(i+1, len(array)):
    if array[min_index] > array[j]:
      min_index = j
    array[min_index], array[i] = array[i], array[min_index]

print(array)

1-2. 列全体の挿入

これは,未処理のデータを選択することにより適切な位置を判断して挿入するアルゴリズムである.
選択ソートと同様に,二重反復文を用いたソートはO(N^2)の時間的複雑さを持つが,データがある程度ソート状態にある場合,選択ソートよりも効率的に適用できる.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
  for j in range(i, 0, -1): #인덱스 i부터 1까지 1부터 감소
    if array[j] < array[j-1]: 
      array[j], array[j-1] = array[j-1], array[j]
    else:
      break #현재 반복문 종료, 다음 반복 강제 실행

print(array)

1-3. クイックソート

基準データ(pivot)を設定し、pivot値を基準に、小さなデータと大きなデータをナビゲートして変換し、pivotに基づいてデータパケットを行います.
マージソートと同様に、通常のソートアルゴリズムによく使用されるアルゴリズムであり、プログラミング言語自体をソートライブラリとして使用することもできます.
基本クイックソートは、最初のデータを基準データ(pivot)に設定し、データパケット後、各データセットに対してクイックソートを繰り返し呼び出します.
時間的複雑度は平均O(N*logN)であり,ある程度並べ替えが行われているとpivotは並べ替えに偏り,複雑度をO(N^2)に増加させる.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
  if start >= end : #정렬원소가 1개일 경우 정렬완료, 재귀종료
    return #정렬된 상태이므로 별도 반환 값이 없어도 됨
    		#전체 함수의 return을 유심히 살펴볼 것
  pivot = start
  left = start+1
  right = end

  while left <= right:
    #피벗보다 큰 데이터
    while left <= end and array[left] < array[pivot]:
      left = left+1
    #피벗보다 작은 데이터
    while right > start and array[right] > array[pivot]:
      right = right-1
    if left <= right: #엇갈리지 않은 경우
      array[left], array[right] = array[right], array[left]
    else : #엇갈린 경우
      array[right], array[pivot] = array[pivot], array[right]
  
  quick_sort(array, start, right-1)
  quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

※Pythonのコードはシンプルで、複数の機能を簡単に実現でき、コードを簡潔に表現できます.
関数全体を用いた場合,関数の戻り値が存在するか,あるいはどのような形で返されるかを判断することで,再帰条件などの戻り文をうまく設定できる.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
  print(array)
  if len(array) <= 1: 
    #left_side에서 첫번째 원소가 0일 경우, array가 empty될 수 있음
    #따라서 탈출조건은 empty경우를 고려하여 =< 1이 되는 것이 좋음
    return array
  
  pivot = array[0] #pivot값
  tail = array[1:] #pivot을 제외한 리스트

  left_side = [x for x in tail if x <= pivot] 
  #데이터묶음을 pivot보다 작은 값들로
  right_side = [x for x in tail if x > pivot]
  #데이터묶음을 pivot보다 큰 값들로

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

1-4. ソケット数

特定の条件下(データサイズ範囲が限られており、整数で表すことができる)では、非常に迅速にソートできる方法です.
時間複雑度は常にO(N+K)(Nはデータ個数、Kはデータ中の最大値)である.
同じデータが複数回現れると、それを有効に利用することができます.

1-5. 適用例

A,Bの配列が2つあります.
2つの配列はN個の元素からなり,いずれも自然数である.
この場合、K回まで置換することができ、置換はA、Bを配列する要素を交換することを意味する.
アルゴリズムを最終アレイAの要素と最大に設定する場合、作成できるアレイAのすべての要素値の合計の最大値は?

の最初の行で、N、Kはスペースを基準に入力されます.

第2行入力配列A、第3行入力配列B.

このときの核心思想は,配列Aの中から最小の要素を毎回選び,配列Bの最大の要素を置き換えることである.

Aは昇順、Bは降順、

置換

Aの要素がBより小さい場合にのみ、

が行われる.

import sys
n, k = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

a.sort()
b.sort(reverse=True)

for i in range(k):
    if a[i] < b[i]:
        a[i], b[i] = b[i], a[i]
    else:
        break #바로 다음 반복문 실행

print(sum(a))

2.ソート間比較