[SW将校学校ジャングル]WEEK 01開発ログ-III

ツールバーの

ソートは
ソートは、名前、学号、単位などのキーをプロジェクト値のサイズ関係に従ってデータセットを一定の順序で並べ替える操作です.データをソートすると、検索が容易になります.小さいデータを前に並べて昇順ソートと呼び、逆に降順ソートと呼ぶ.
泡の位置合わせ
泡ソートは、後から前へソートされる構造を有する.昇順ソートを基準として、最高値を配列の最後の空間に送信し、その前に2番目の大きな値を送信します.「そのためには、アレイ内の値を前後に比較し、シフト操作を繰り返します.」「小さい値を前に持ち込む」という概念を利用して、大きな値を後ろに送信し、要素間の位置変更の様子を水滴移動のようにすることから、BubbleSortと名付けられた.

버블 정렬 구현

def bubble_sort(arr):
	for i in range(len(arr)-1, 0, -1): # 뒤에서 부터 정렬한다.
    	for j in range(len(i)): 	   # 앞에서 부터 조회
        	if arr[j] > arr[j+1]:      # 인근 값 대소 비교
            	arr[j], arr[j+1] = arr[j+1], arr[j]

バブルソートは、大きな値を後ろから1つずつ前に積み上げるので、要素が位置するとソートの範囲が1つ減少します.最小値を探して最前面に配置する選択ソートとは逆です.他のソートアルゴリズムと比較して,値のswapが頻繁に発生する.
時間の複雑さは、ループ文を介してすべてのインデックスにアクセスする必要があるため、基本的にO(N)の時間が必要であり、1つのループは隣接する要素と比較および交換するために追加のO(N)の時間が必要である.したがってBubbleソートはO(N^2)の複雑さを持つソートアルゴリズムである.
ソートの選択
ソートの選択は、ソートされていないデータの中から最小のデータを選択し、先頭から順番にソートするアルゴリズムです.ソートの先頭からソート後の値を1つずつ入力するように選択します.したがって、インデックスの比較範囲が後になるほど小さくなるという特性があります.入力配列がソートされているかどうかにかかわらず、同じ演算量を持つため、最適化の余地が小さく、パフォーマンスが低下します.

선택 정렬 구현

def selection_sort(arr):
	for i in range(len(arr) -1):  # outer
    	min_idx = i
        for j in range(i+1, len(arr)): # inner
        	if arr[j] < arr[min_idx]"  # 최저값을 찾아내면
            	min_idx = j			   # 최저값의 idx를 가져온다.
        arr[i], arr[min_idx] = arr[min_idx], arr[i] # value swap
    return arr

ソートを選択するには、すべてのインデックスにループ文でアクセスする必要があるため、デフォルトではO(N)時間が必要です.最小値が見つかった場合は、現在のインデックスと最小値を交換する必要があるため、O(N)時間が必要です.従って,選択ソートは全O(n^2)時間の複雑さを持つソートアルゴリズムである.
整列挿入
ソートを挿入すると、すべての要素が前からソート範囲に拡張され、ソートされます.並べ替えられた並べ替え部分と拡張された範囲部分を順番に比較し、自分の位置を見つけて挿入することで並べ替えのアルゴリズムを完了します.以前に観察した選択や泡の並べ替えとは異なり,並べ替えが進むほど範囲が広がる.大きな角度から見ると、外輪は順方向で、内輪は逆方向で、繰り返します.

삽입 정렬 구현

def insertion_sort(arr):
	for end in range(1, len(arr)):
    	for i in range(end, 0, -1):
        	if arr[i-1] > arr[i]:
            	arr[i]. arr[i-1] = arr[i-1], arr[i]
    return arr

挿入ソートは、ループ文によってソート範囲を2つからグローバルに拡張するため、基本的にはO(N)時間、ソート範囲に追加される値、および既存の値とのサイズ比較と交換に必要なO(N)時間が消費されます.したがって,挿入ソートはO(N^2)時間の複雑さを持つソートアルゴリズムである.
クイックソート
高速ソートは,分割征服技術と再帰アルゴリズムを用いたソートアルゴリズムである.クイックソートではpivot(任意の基準値)という変数が導入されます.クイックソートはpivot値を基準に、より小さな値とより大きな値で分割を繰り返し、ソートする方式です.

퀵 정렬 구현

def quick_sort(arr):
    if len(arr) == 1:
        return arr
    pivot = arr[len(arr)//2]
    lesser_list, equal_list, greater_list = [], [], []
    for i in arr:
        if i < pivot:
            lesser_list.append(i)
        elif i > pivot:
            greater_list.append(i)
        else:
            equal_list.append(i)
    return quick_sort(lesser_list) + equal_list + quick_sort(greater_list)

高速ソートのパフォーマンスは、ピボット値の選択によって大きく変化する可能性があります.理想的には、小さい値と大きい値を同じ個数に分割すると、O(Nlogn)の時間的複雑さがある.しかし,誤ったpivotが選択されて値が一方に偏ると,高速ソートの性能が低下し,最悪の場合O(n^2)の時間的複雑さが表示される.
連結ソート
マージソートは,高速ソートと同様に,分割征服技術と再帰アルゴリズムを用いたソートアルゴリズムである.指定された配列のサイズが1になる前に、半分に分割し、並べ替えてマージします.

병합 정렬 구현

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0

    while l < len(left) and h < len(right):
        if left[l] < right[h]:
            merged_arr.append(left[l])
            l += 1
        else:
            merged_arr.append(right[h])
            h += 1
    merged_arr += left[l:]
    merged_arr += right[:h]
    return merged_arr

連結ソートは、分割と連結の2つの段階に大別され、中間インデックスのみを検索する分割コストよりも、すべての値の連結コストが高くなります.既存のアレイを分割する場合,繰返し回数は8>4>2>1の大きさで半分に減少するため,O(logn)の時間が必要であり,マージ時にはすべての値を比較する必要があるため,O(N)の時間が必要である.したがって,集計ソートはO(Nlogn)の時間的複雑さを持つ.
並べ替えに関する白文問題Githubリンク
バックグラウンド・ソートに関する問題