WEEK. 01 2022.04.04 TIL

クイックソート

def pivot_sort(a, left, right): # 배열, 정렬 대상의 양쪽 끝 값
    n = len(a)
    pl = left
    pr = right
    pivot = a[(pl+pr)//2]
    while pl <= pr: 
        while a[pl] < pivot: pl += 1
        while a[pr] > pivot: pr -= 1    
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
    # 종료조건, left 및 right가 pr, pl에 도달하면 정렬이 완료되었다고 판단함.
    if pr > left: pivot_sort(a, left, pr+1)
    if pl < right: pivot_sort(a, pl, right)

スタック

スタックは一時的にデータを格納するためのデータ構造であり、データの入出力順序は「後入先出」(LIFO)である.
LIFO(ast in firstout)とは、最後に入れたデータを最初に取り出すことです.
スタックレイアウト:stk

ブール型データを格納するスタックホストリスト型アレイで、インデックスが0の要素をスタック下部と呼ぶ.

スタックサイズ:容量

スタックの最大サイズを表す整数で、配列stkの要素数len(stk)と一致します.

スタックポインタ:ptr
Null値は、

スタックに蓄積されたデータの個数を表し、0であれば容量に等しい.

スタックの非再帰的な高速ソートの使用

ソートする要素の範囲をスタックにプッシュし、スタックが空(ソートする範囲がない)の場合、閉じた文を作成します.

 range = Stack(right-left+1) # stack 생성
 range.push((left, right))
  while not range.is_empty(): # stack이 비어있으면 정렬 종료
      pl, pr = left, right = range.pop() # stack의 top에 위치한 정렬 범위를 의미하는 원소를 추출
      x = a[(left + right) // 2] # 피봇값

      # 퀵 정렬 알고리즘

      if left < pr: range.push((left, pr)) # pr이 left에 도달하면 정렬이 종료하므로 stack이 비어있게 되어 정렬 종료
      if pl < right: range.push((pl, right))

配列をスタックにプッシュする場合、大量の要素のページをプッシュ(後でプッシュ)することで、スタックのサイズを効果的に小さくすることができます.
ピボットを選択すると、片側に偏った値を選択すると、効率が低下する可能性があります.この問題を解決するには、アレイから任意の3つの要素を取り出し、中心要素を軸として選択することが望ましい.

クイックソート-ピボットの選択方法の変更

ピボットを効率的に選択するには、コードを変更して、配列の最初の値、中心値、および最後の値を抽出してソートし、ピボットを選択します.この方法に並べ替えられた標準2751号の問題は、タイムアウトのため解決できない.

def selection_mid(a, b, c): # 세 값을 정렬하는 함수
    if b > c: b, c = c, b
    if a > b: a, b = b, a
    if b > c: b, c = c, b
    return a, b, c

def quick_sort(a, left, right):
    pv_index = (left + right) // 2
    a[left], a[pv_index], a[right] = selection_mid(a[left], a[pv_index], a[right])
    a[pv_index], a[right-1] = a[right-1], a[pv_index] # pivot에 위치하는 값을 right-1 위치의 원소와 교환
    pl = left + 1 # 첫번째 원소는 이미 정렬을 완료했으므로 pl 범위가 수정됨.
    pr = right - 2 # right 및 right-1 원소 또한 정렬을 완료했으므로 pr값이 수정됨.
    pivot = a[right-1]
    while pl <= pr:
        while a[pl] < pivot: pl += 1
        while a[pr] > pivot: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
    if pr > left: quick_sort(a, left, pr+1)
    if pl < right: quick_sort(a, pl, right)

連結ソート

アレイを特定の基準に分割し、分割されたアレイをソートおよびマージする方法.あまり理解できないので以下のように書きます.

以下は,自分の考えに基づいて,意識フローに従って記述されたコードであり,未知のエラーが多数発生している.

def merge_sort(a, left, right):
    center = (left + right) // 2
    if right > left: # 배열의 끝 인덱스가 첫번째 인덱스와 같아지는 즉, 배열의 크기가 1이 될때까지 실행
        merge_sort(a, left, center) # 배열 분류
        merge_sort(a, center, right)
        
    # 병합 부분
    a1 = a[left:center] # left부터 center 전까지
    a2 = a[center:right+1] # center부터 right까지
    n1 = len(a1) # a1 배열 크기
    n2 = len(a2) # a2 배열 크기
    temp_3 = [] # a1과 a2를 정렬하기 위한 임시 배열
    i = 0 # a1 인덱스
    j = 0 # a2 인덱스
    while i < n1 and j < n2: # a1 혹은 a2의 인덱스가 배열의 끝에 도달하면 종료
        if a1[i] >= a2[j]:
            temp_3 += a1[i]
            i += 1
        elif a1[i] < a2[j]:
            temp_3 += a2[j]
            j += 1
    if i < n1: # 종료 시점에서의 인덱스가 배열의 크기보다 작을 경우 남은 원소들을 temp 배열에 추가
        temp_3 += a1[i:n1]
    if j < n2:
        temp_3 += a2[j:n2]
    a[left:right+1] = temp_3 # 타겟 배열 범위를 temp로 수정
    return

次は修正したコードです.
まず、merge sortを終了する条件が要素が1つである場合、マージできないためエラーが発生します.変更します.
また、私が今適用している方法は、例えば、2つの要素がある場合、2つの要素をa 1、a 2に分けて小数からtempという一時配列に入れ、元の配列aの対応する位置に入れるが、center値をleft+rightのシェアに設定するので、leftとcenter値は同じになる.
この場合、a 1[left:center]のleftとcenterは同じであるため、この配列は空であり、エラーを引き起こす.変更します.

import sys
sys.setrecursionlimit(10**5)
n = int(input())
a = [int(sys.stdin.readline()) for i in range(n)] 

def merge_sort(a, left, right):
    center = (left + right) // 2
    if right > left:
        merge_sort(a, left, center)
        merge_sort(a, center+1, right)
        a1 = a[left:center+1]
        a2 = a[center+1:right+1]
        n1 = len(a1)
        n2 = len(a2)
        temp_3 = []
        i = 0
        j = 0
        while i < n1 and j < n2:
            if a1[i] >= a2[j]:
                temp_3.append(a2[j])
                j += 1
            elif a1[i] < a2[j]:
                temp_3.append(a1[i])
                i += 1
        if i < n1:
            temp_3 += a1[i:n1]
        if j < n2:
            temp_3 += a2[j:n2]
        a[left:right+1] = temp_3
        
merge_sort(a, 0, len(a)-1)
for x in a:
    print(x)