[イコタ]配列

📚 コンセプト

ソートとは、特定の基準に従ってデータを順番にリストすることです.プログラムでデータを加工する場合、通常は昇順や降順など多様な方法でソートされるため、ソートアルゴリズムはプログラムを作成する際に最もよく使われるアルゴリズムの一つである.しかし、状況に合わないソートアルゴリズムを使用すると、プログラムの実行効率はもちろん低く、時間も必要以上にかかります.ソートアルゴリズムもバイナリ検索の前処理プロセスです.

ソートの選択

データがランダムに複数存在する場合、最小のデータを先頭のデータに置き換え、小さいデータを選択して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[i], array[min_index] = array[min_index], array[i]

print(array)

テーブル選択ソートの時間的複雑さ

ソートを選択して、N-1番の最小数を見つけて一番前に送信します.また,毎回比較演算を用いて最小の数を探す必要がある.実施形態によっては多少の誤差があるかもしれないが、前述のように計算回数はN+(N−1)+(N−2)+…+2と見ることができます.したがって,近似値を用いてNx(N+1)/2次演算を行うと仮定する.これは(n^2+n)/2で表すことができ,bigoマーキング法でO(n^2)と簡単に表すことができる.
重複文が重なる程度によって,時間の複雑さを簡単に判断できる.選択ソートの時間的複雑度はO(N^2)である.直感的には、ソースコードに単純な形式の2つの重複文が使用されていると理解できる.基本ソート・ライブラリを含む他のアルゴリズムに比べて、ソートの選択は非常に効果的ではありません.

挿入

1つずつデータを確認し、各データを適切な位置に挿入するアルゴリズム.挿入ソートは選択ソートに比べて実現が困難であるが,選択ソートに比べて実行時間の面でより効率的なアルゴリズムである.特に、挿入ソートは必要に応じてのみ位置を変更するので、「データがほぼ整列している場合」の方が効率的です.挿入ソートは、特定のデータを適切な場所に「挿入」することを挿入ソートと呼びます.また、挿入ソートは、あるデータが適切な位置に入る前に、前のデータが整列していると仮定します.

📌 サンプルコード

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):
        if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

テーブル挿入ソートの時間的複雑さ

挿入ソートの時間的複雑度はO(N^2)であり,選択ソートと同様に繰り返し文を2回重ねて用いた.重要な点は、現在のリストにソートされたデータがほぼ整列している場合、その動作が非常に速いことです.最適の場合,O(N)の時間的複雑さを持つ.高速ソートアルゴリズムと比較して、通常、挿入ソート効率は低く、または高速ソートアルゴリズムよりもほとんどソートされていない場合が強い.したがって、入力がほぼ整列している場合は、クイックソートなどの他のソートアルゴリズムを使用するよりも、挿入ソートを使用することが望ましい.

クイックソート

これは、基準データを設定し、ビッグデータとビッグデータの位置を変更するアルゴリズムです.クイックソートは、標準を設定し、大数と小数を交換し、リストを半分にする方法です.クイックソートではピボット(Pivot)を使用します.大きな数字と小さな数字を交換するとき、交換する「標準」が軸です.「≪クイック・ソート｜Quick Sort｜Essbase_Studio≫」で、特定のリストにピボットを設定してソートし、ピボットに基づいて左側のリストと右側のリストでそれぞれ並べ替えます.

📌 サンプル・コード-直感的なクイック・ソート・コード

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

def quick_sort(array, start, end):
    # 원소가 1개인 경우 종료
    if start >= end:
        return
    pivot = start # 피벗은 첫 번재 원소
    left = start+1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

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

📌 サンプル・コード-単純な形式のクイック・ソート・コード

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

def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

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

print(quick_sort(array))

高速ソートの時間的複雑さ

高速ソートの時間的複雑さはO(Nlogn)である.しかし最悪の場合,時間的複雑度はO(N^2)である.データがランダムに入力されている場合は、クイックソートがすばやく実行される可能性があります.しかし、データがソートされている場合、その動作は非常に遅いです.前述した挿入ソートは、データがソートされている場合に非常に速く実行され、高速ソートとは逆であることが理解される.

ソート係数

カウントソートアルゴリズムは、特定の条件を満たす場合にのみ使用できる非常に高速なソートアルゴリズムです.すべてのデータが正の整数であると仮定します.データの個数がNであり、データの中で最もコストが大きい値がKである場合、カウントソートは最悪の場合でも実行時間O(N+K)を保証する.係数ソートはこのように迅速であり,原理も非常に簡単である.ただし、カウントソートは「データのサイズ範囲が限られており、整数で表す場合にのみ使用できます」としています.例えば、与えられたデータの値が無限範囲の実数型データを有する場合、係数ソートを用いることは困難である.通常、最大と最小のデータの差が1000000を超えない場合、それらを有効に使用することができる.
例えば、0以上100以下の成績データをソートする場合、カウントソートは有効です.ただし、最大データと最小データの差が大きすぎると、係数ソートは使用できません.係数ソートがこのような特徴を持つのは、係数ソートを使用する場合、「すべての範囲のサイズリスト(配列)を含めることができる」と宣言する必要があるからです.たとえば、最大データと最小データの差が1000000の場合、合計1000001個のデータを格納できるリストを初期化する必要があります.
カウントソートは、前述したソートアルゴリズムとは異なり、データ値を直接比較し、位置を変更してソートする方法(比較に基づくソートアルゴリズム)ではありません.

📌 サンプルコード

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

count = [0] * (max(array) + 1)
for i in array:
    count[i] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ')

テーブル係数ソートの時間的複雑さ

すべてのデータが正の整数である場合、データの個数がNであり、データの最大値の大きさがKである場合、カウントソートの時間的複雑度はO(N+K)である.データの範囲が限られている限り、効率的に使用でき、常に迅速に動作します.

表係数ソートの空間的複雑さ

係数ソートは、深刻な非効率をもたらす場合があります.たとえば、2つのデータ(0と999999999999セグメント)しかないとします.この場合も、リストの大きさが100万個に達すると発表します.したがって、同じ値を持つ複数のデータを表示するのに適した一般的なソートアルゴリズムではありません.すなわち、カウントソートは限られており、データのサイズが大きいほど、重複するほど有利であり、常に利用可能ではない.係数配列の空間的複雑度はO(N＋K)であった.