ソートアルゴリズム

泡の位置合わせ

2つの隣接要素

をチェックして並べ替えます.

for i = 0 to (arr의 크기-1) do
  for j = 0 to (arr의 크기-2-i) do
    if arr[j]가 arr[j+1]보다 크면
    then arr[j+1]과 arr[j] 교환
    endif
  endfor
endfor

時間複雑度O(N^2)

ソートの選択

アルゴリズム

for i = 0 to (arr의 크기-1) do
  min_index = i
  for j = i to (arr의 크기-1) do
    가장 작은 원소 찾아서 min_index에 넣어주기
    endfor
  arr[i]와 arr[min_index]값 교환
endfor

の順序でn,n-1,n-2...比較すると,時間複雑度はO(N^2)

であった.

整列挿入

並べ替えカード間の正しい位置

に新しいカードを挿入する.

は、2番目の要素から始まり、前の要素と比較する位置

を変更する.

for i = 1 to (arr의 크기-1) do
  index = i-1
  while index가 0보다 크거나 같고 arr[index] > arr[index+1]
    arr[index]와 arr[index+1] 교환
    index-=1
  endwhile
endfor

選択ソートと同様に、

は、最悪の場合(逆ソートの場合)

である.
すべての

が並べ替えられている場合、比較は1回のみであるため、O(N)

連結ソート

要素を半分にし、

を繰り返してマージおよびソートします.

function mergeSort(a: 배열):
  if a의 사이즈가 1보다 작거나 같으면
    return a
  endif
  
  mid = len(a)를 2로 나눈 몫
  left = mergeSort(a[:mid])
  right = mergeSort(a[mid:])
  return merge(left, right)

function merge(left: 배열, right: 배열):
  i = 0, j = 0
  res = []
  while i가 len(left)보다 작고, j가 len(right)보다 작을때
    if left[i] <= right[j]
    then left[i]를 res에 push하고 i 1 증가
    else left[j]를 res에 push하고 j 1 증가
    endif
  endwhile
  
  while i가 len(left)보다 작음
    left[i]를 res에 push하고 i에 1 증가
  while j가 len(right)보다 작음
    left[j]를 res에 push하고 j에 1 증가
  return res

を順番に比較し、チェーンテーブル有効

を使用する.

時間複雑度平均O(N logN)

クイックソート

pivotを基準として、pivotより小さい数とpivotより大きい数の集合に分けられる.

コレクション内でpivotを選択してコレクションに分割するプロセスを繰り返します.

reference

function quickSort(arr: 배열, start: 시작 인덱스, end: 끝 인덱스):
  pivot = start
  left = pivot+1
  right = end
  while left <= right:
      while left < end and arr[left] <= arr[pivot]:
          left += 1
      endwhile
      while right > start and arr[right] >= arr[pivot]:
          right -= 1
      endwhile
      if left <= right:
      then arr[left],arr[right] = arr[right], arr[left]
  endwhile
  arr[right], arr[pivot] = arr[pivot], arr[right]
  quickSort(arr, start, right-1)
  quickSort(arr, right+1, end)

平均O(N log N)

最小値または最大値として

pivotを選択すると、O(N^2)

は分割されない.

お尻の位置合わせ

完全バイナリツリーをベースとしたHIP資料構造をベースとした.

最大hipからheap sort で最大値を抽出してソートします.
平均

時間複雑度O(Nlogn)

,最適および最悪

最大または最小値を求める場合、最大の数だけを求める場合に有効です.