ソートSorting


これはPythonを読んでコードテストを行う文章です.

ツールバーの


≪ソート|Sort|Planning≫:データを特定の条件の順序でリストします.

ソートの選択


≪ソートの選択|Select Sort|Planning≫:最小のデータを選択し、先頭のデータと置換プロセスを繰り返しソートします.
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)
時間複雑度:O(N^2)

整列挿入


≪位置合わせの挿入|Insert Align|Planning≫:特定のデータの位置合わせを適切な位置に挿入します.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(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)は、位置合わせに近い状態で非常に速く動作します

クイックソート


≪クイック・ソート|Quick Sort|oem_src≫:データム・データを設定し、データムより大きいデータとデータムより小さいデータを再配置するソート
ピボットピボット:互換規格こうかんきじゅん
array = [7, 5, 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)、位置合わせ状態に近づくと動作が非常に遅くなります

ソート数


≪係数ソート|Factor Sort|oem_src≫:特定の条件が満たされている場合にのみ使用できますが、ソート速度は非常に速いです.
条件:データのサイズ制限は整数でなければなりません.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

count = [0] * (max(array) + 1)
for i in range(len(array)):
    count[array[i]] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')
時間の複雑さ:O(N+K)、K(最大値)、データサイズが限られており、重複性が大きい場合の利点

Pythonソートライブラリ

  • sort(), sorted():集計順によるO(Nlogn)
  • [問題]上から下へ


    数の大小にかかわらず並んでいます.
    降順でソートするプログラムを作成してください.
    ->ソート・ライブラリの使用、逆降順ソートの使用
    # 내 풀이
    n = int(input())
    
    array = [0] * n
    for i in range(n):
        array[i] = int(input())
    
    array.sort(reverse=True)
    
    for data in array:
        print(data, end=' ')

    [問題]成績の低い順に学生を印刷する


    N人の学生の情報は名前と成績に分けられる.
    成績の低い順に学生の名前を印刷するプログラムを作成してください.
    ->ソートライブラリを使用し、lambdaを使用して特定の条件でソート
    # 내 풀이
    n = int(input())
    array = []
    for i in range(n):
        name, score = input().split()
        array.append([name, int(score)])
    
    array = sorted(array, key=lambda k:k[1])
    
    for data in array:
        print(data[0], end=' ')

    [問題]2つの配列の要素を置換


    A,Bの2つの配列はN個の元素からなり,いずれも自然数である.
    K回までの巴果打数演算が可能です.
    Aのすべての要素の和を最大にするプログラムを作成してください.
    ->ソートライブラリの使用、swapの使用
    # 내 풀이
    n, k = map(int, input().split())
    arrayA = sorted(list(map(int, input().split())))
    arrayB = sorted(list(map(int, input().split())), reverse=True)
    
    12345
    54432
    for i in range(k):
        if arrayA[i] >= arrayB[i]: break
        arrayA[i], arrayB[i] = arrayB[i], arrayA[i]
    
    print(sum(arrayA))