ツールバーの

ソートアルゴリズムには、一般的な選択ソート、挿入ソート、クイックソート、カウントソートが含まれます.
使うことが多いので、この4つの方法を試してみたいと思います.
ソートアルゴリズムを学習することによって,アルゴリズム効率の重要性を認識することが望ましい.

1.ソート選択（Selection Sort）

データがランダムに複数表示される場合.2つの最小データを選択し、一番前のデータを置き換えます.
次に、小さなデータを選択し、2番目のデータと交換するプロセスを前に繰り返します.
毎回、「最小選択」の意味で選択ソートを行います.

コード実装

array = [5, 1, 3, 7, 2, 9]

for i in range(array.__len__()):
    minNum = i  ## 제일 작은 인덱스 저장.
    for j in range(i+1, array.__len__()):
        if array[minNum] > array[j]:
            minNum = j

    array[i], array[minNum] = array[minNum], array[i]


print(array)

時間的複雑度はO(N^2)である.効率は低いが、符号化テストでは特定のリストの最小データを検索することが多いため、ソートソースコードの選択形式を熟知する必要がある.

2.ソートの挿入

挿入ソートは、必要に応じてのみシフトされるので、「データがほぼ整列している場合」は本当に効率的です.

コード実装

array = [5, 1, 3, 7, 2, 9]

for i in range(len(array)-1):
    for j in range(i+1, 0, -1): ## (start,end,step) end=0 이면 0까지 실행하는게아니라 1까지 실행함
        if array[j] > array[j-1]:
            break
        array[j], array[j-1] = array[j-1], array[j]


print(array)

最悪の場合,時間的複雑度はO(N^2)である.でも一番いいのはO(N)で、ほぼ並べ替えが整えれば、非常に素早く並べ替えられます.

3.クイックソート

クイックソートは、これまでに学んだソートで最も多く使用されたアルゴリズムです.
クイックソートでは、ピボット軸を使用します.

コード実装

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


def quick(array, start, end):
    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 start < right and array[right] >= array[pivot]:
            right -= 1
        if left > right:  # 엇갈리면 피벗이랑 교환
            array[right], array[pivot] = array[pivot], array[right]
        else:  # 안 엇갈렷으면 작은데이터와 큰 데이터 교환
            array[right], array[left] = array[left], array[right]
    quick(array, start, right-1)
    quick(array, right+1, end)


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

高速ソートの平均時間複雑度はO(Nlogn)であるが,最悪の場合O(N^2)に達する可能性がある.この場合、配列がほぼ1つの並べ替えになると、このようになります.

4.ソート数

これは、特定の条件を満たす場合にのみ使用できる非常に高速なソートアルゴリズムです.カウントソートが最悪の場合,時間的複雑度はO(N+K)であるが,条件がある.
1.データ値は整数でなければなりません.負の値は指定できません.
2.通常、インクリメンタルデータと最小データとの差が1000000を超えない場合に有効に使用できます.
最大と最小のデータの差が大きすぎる場合は、カウントソートを使用しないほうが効果的です.

array = [5, 2, 1, 5, 6, 1, 3, 8]

array2 = [0]*(len(array)+1)

for i in array:
    array2[i] += 1

for i in range(len(array2)):
    for j in range(array2[i]):
        print(i, end=",")

サイズが限られており、重複するデータが大きいほど、ソートカウントが容易になり、書き込みが常に困難になります.これらの条件を満たす限り,係数ソートは非常に高速なアルゴリズムである.