Gruntle Software & Testing

Python 정렬: Python의 정렬 방법 및 알고리즘

작성자 Stewart Tristian게시일 게시 위치 가이드

Python에서 다양한 정렬 방법과 알고리즘을 사용하여 목록, 배열, 사전 등을 정렬하기 위해 Python Sort 함수를 사용하는 방법을 알아보세요.

정렬은 정렬에 사용되는 기술입니다. 데이터를 오름차순 또는 내림차순으로 정렬합니다.

대부분의 경우 대형 프로젝트의 데이터는 올바른 순서로 정렬되지 않으며 이로 인해 필요한 데이터에 효율적으로 액세스하고 가져오는 데 문제가 발생합니다.

이 문제를 해결하기 위해 정렬 기술이 사용됩니다. 파이썬은 예 버블 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등 다양한 정렬 기술을 제공합니다.

이 자습서에서는 다양한 알고리즘을 사용하여 Python에서 정렬이 작동하는 방식을 이해합니다.

파이썬 정렬

파이썬 정렬 구문

정렬을 수행하기 위해 Python은 내장 함수, 즉 " sort() " 함수를 제공합니다. 목록의 데이터 요소를 오름차순 또는 내림차순으로 정렬하는 데 사용됩니다.

예제를 통해 이 개념을 이해해 보겠습니다.

예제 1: 

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```

Output:

이 예제에서 주어진 정렬되지 않은 목록은 " sort( ) " 함수를 사용하여 오름차순으로 정렬됩니다. .

예 2: 

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```

출력

위의 예에서 주어진 정렬되지 않은 목록은 " sort( reverse = True ) " 함수를 사용하여 역순으로 정렬됩니다.

시간장소 버블정렬 O(n) O(n2) O(n2) O(1) 예 예 삽입 정렬 O(n) O(n2) O(n2) O(1) 예 예 빠른 정렬 O(n log(n)) O(n log(n)) O(n2) O(N) 아니오 예 병합 정렬 O(n log(n)) O(n log(n)) O(n log(n)) O(N) 예 아니오 힙 정렬 O(n log (n)) O(n log(n)) O(n log(n)) O(1) 아니오 Yes

위 비교표에서 “O”는 위에서 설명한 Big Oh 표기법이고 “n”과 “N”은 입력의 크기를 의미한다. .

자주 묻는 질문

Q #1) Python에서 sort()가 무엇입니까?

답변: Python에서 sort()는 목록이나 배열을 특정 순서로 정렬하는 데 사용되는 함수입니다. 이 기능은 대규모 프로젝트에서 작업하는 동안 정렬 프로세스를 용이하게 합니다. 개발자에게 많은 도움이 됩니다.

Q #2) 파이썬에서는 어떻게 정렬하나요?

답변: Python은 요소를 정렬하는 데 사용되는 다양한 정렬 기술을 제공합니다. 예 퀵정렬, 병합정렬, 버블정렬, 삽입정렬 등 모든 정렬 기법이 효율적이고 이해하기 쉽습니다.

Q #3) 파이썬은 어떻게 정렬() 작업?

답변: 정렬()함수는 주어진 배열을 사용자의 입력으로 받아 정렬 알고리즘을 사용하여 특정 순서로 정렬합니다. 알고리즘 선택은 사용자 선택에 따라 다릅니다. 사용자의 필요에 따라 Quick Sort, Merge Sort, Bubble Sort, Insertion Sort 등을 사용할 수 있습니다. 일반적인 정렬 기술.

  • 버블 정렬
  • 삽입 정렬
  • 퀵 정렬

우리는 그들의 시간 복잡도와 장점 & 단점. 또한 위의 모든 기술을 비교했습니다.

정렬 알고리즘의 복잡성

시간 복잡도는 컴퓨터가 특정 알고리즘을 실행하는 데 걸리는 시간입니다. 세 가지 유형의 시간 복잡도 사례가 있습니다.

  • 최악의 사례: 컴퓨터에서 프로그램을 실행하는 데 걸리는 최대 시간.
  • 평균 사례: 컴퓨터가 프로그램을 실행하는 데 최소 시간과 최대 시간 사이에 걸리는 시간.
  • 최고 사례: 컴퓨터가 프로그램을 실행하는 데 걸리는 최소 시간. 시간 복잡도가 가장 좋은 경우입니다.

Complexity Notations

Big Oh Notation, O: Big Oh Notation은 상한을 전달하는 공식적인 방법입니다. 알고리즘의 실행 시간. 최악의 경우 시간 복잡도를 측정하는 데 사용되거나 알고리즘이 완료하는 데 걸리는 최대 시간을 말합니다.

빅 오메가 표기법, : 빅 오메가 표기법은 알고리즘 실행 시간의 최저 경계를 전달하는 공식적인 방법입니다. 최상의 경우의 시간 복잡도를 측정하는 데 사용되거나 알고리즘에 소요되는 우수한 시간을 말합니다.

Theta 표기법, : Theta 표기법은 두 경계, 즉 알고리즘이 완료하는 데 걸리는 시간의 하한 및 상한.

Python의 정렬 방법

버블 정렬

버블 정렬은 데이터를 정렬하는 가장 간단한 방법입니다. 무차별 대입 기술을 사용합니다. 각 데이터 요소를 반복하고 다른 요소와 비교합니다.사용자에게 정렬된 데이터를 제공합니다.

이 기술을 이해하기 위해 예를 들어 보겠습니다.

  • 우리는 " 10, 40, 7, 3, 15”. 이제 Python의 버블 정렬 기술을 사용하여 이 배열을 오름차순으로 정렬해야 합니다.
    • 첫 번째 단계는 배열을 주어진 순서대로 정렬하는 것입니다.
    • "반복 1"에서는 배열의 첫 번째 요소를 다른 요소와 하나씩 비교합니다.
    • 빨간색 화살표는 첫 번째 요소를 배열의 다른 요소와 비교하는 것을 설명합니다.
    • " 10 "이 " 40 "보다 작으므로 동일하게 유지됩니다. 하지만 다음 요소 "7"은 "10"보다 작습니다. 따라서 교체되어 1위가 됩니다.
    • 위의 과정을 반복하여 요소를 정렬합니다.

    • " 반복 2 "에서 두 번째 요소는 배열의 다른 요소와 비교됩니다.
    • 비교된 요소가 작으면 그렇지 않으면 같은 위치에 남게 됩니다.

    • In " Iteration 3 " 세 번째 요소는 배열의 다른 요소와 비교됩니다.

    • 마지막으로 " 반복 4 " 두 번째 마지막 요소가 배열의 다른 요소와 비교됩니다.
    • In이 단계에서 배열은 오름차순으로 정렬됩니다.

버블 정렬용 프로그램 

``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ```

출력

버블 정렬의 시간 복잡도

  • 최악의 경우: 버블 정렬의 최악의 시간 복잡도는 O( n 2)입니다.
  • 평균적인 경우: 버블 정렬의 평균 시간 복잡도는 O( n 2).
  • 가장 좋은 경우: 버블 정렬의 가장 좋은 시간 복잡도는 O(n)입니다.

장점

  • 대부분 사용되며 구현하기 쉽습니다.
  • 단기 스토리지를 소비하지 않고 데이터 요소를 교환할 수 있습니다.
  • 더 적게 필요합니다.

단점

  • 대량의 데이터 요소를 많이 처리하면서 성능이 좋지 않았다.
  • 그것은 정렬하려면 각 "n"개의 데이터 요소에 대해 n 2단계가 필요합니다.
  • 실제 응용 프로그램에는 좋지 않습니다.

삽입 정렬

삽입 정렬은 카드를 정렬하는 것과 유사하게 작동하는 쉽고 간단한 정렬 기술입니다. 삽입 정렬은 각 요소를 하나씩 비교하여 요소를 정렬합니다. 요소가 다른 요소보다 크거나 작은 경우 해당 요소를 선택하고 다른 요소로 교체합니다.

예를 들어 보겠습니다.

  • 우리는 요소가 " 100, 50, 30, 40, 10 "인 배열입니다.
  • 먼저 배열을 정렬하고 비교를 시작합니다.
  • 첫 번째 단계에서 "100"은 두 번째 요소인 "50"과 비교됩니다. " 50 "은 크기가 클수록 " 100 "과 교체됩니다.
  • 두 번째 단계에서 다시 두 번째 요소 "100"은 세 번째 요소 "30"과 비교되어 교체됩니다.
  • 이제 " 30 "이 다시 " 50 "보다 작기 때문에 첫 번째 위치에 오는 것을 발견하면
  • 배열의 마지막 요소까지 비교가 발생하고 마지막에 우리는 다음을 얻을 것입니다. 정렬된 데이터.

삽입 정렬용 프로그램 

``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value  array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ```

출력

삽입 정렬의 시간 복잡도

  • 최악의 경우: 삽입 정렬의 최악의 시간 복잡도는 O( n 2).
  • 평균 사례: 삽입 정렬의 평균 시간 복잡도는 O( n 2)입니다.
  • 가장 좋은 경우: 삽입 정렬의 가장 좋은 시간 복잡도는 O(n)입니다.

장점

  • 간단합니다. 구현이 용이합니다.
  • 소수의 데이터 요소를 처리하면서 성능이 우수합니다.
  • 구현을 위해 더 많은 공간이 필요하지 않습니다.

단점

  • 많은 데이터 요소를 정렬하는 것은 도움이 되지 않습니다.
  • 다른 정렬 기술에 비해 성능이 좋지 않습니다.

병합 정렬

이 정렬 방법은 요소를 특정 순서로 정렬하기 위해 분할 및 정복 방법을 사용합니다. 병합 정렬을 사용하여 정렬하는 동안,요소를 반으로 나눈 다음 정렬합니다. 모든 절반을 정렬한 후 요소가 다시 결합되어 완벽한 순서를 형성합니다.

이 기술을 이해하기 위해 예를 들어 보겠습니다.

  • 우리는 다음과 같이 제공됩니다. 배열 " 7, 3, 40, 10, 20, 15, 6, 5 ". 배열에는 7개의 요소가 포함되어 있습니다. 반으로 나누면( 0 + 7 / 2 = 3 ).
  • 두 번째 단계에서 요소가 두 부분으로 나뉘는 것을 볼 수 있습니다. 각각에는 4개의 요소가 있습니다.
  • 또한 요소는 다시 분할되어 각각 2개의 요소를 가집니다.
  • 이 프로세스는 배열에 하나의 요소만 존재할 때까지 계속됩니다. 단계 번호를 참조하십시오. 그림에서 4번입니다.
  • 이제 요소를 정렬하고 분할된 대로 결합하기 시작합니다.
  • 단계 no. 5 7이 3보다 크면 교환하고 다음 단계에서 조인하고 그 반대의 경우도 마찬가지입니다.
  • 마지막에 배열이 오름차순으로 정렬되고 있음을 알 수 있습니다.

병합정렬 프로그램 

``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i  len(L) and j  len(R): if L[i]  R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i  len(L): arr[k] = L[i] i += 1 k += 1 while j  len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ```

출력

병합 정렬의 시간 복잡도

  • 최악의 경우: 병합 정렬의 최악의 시간 복잡도는 O( n log( n )).
  • 평균 사례: 병합 정렬의 평균 시간 복잡도는 O( n log( n )).
  • 최상의 경우: 병합 정렬의 최적 시간 복잡도는 O( n log( n )).

장점

  • 이 정렬 기술에서는 파일 크기가 중요하지 않습니다.
  • 이 기법은 일반적으로 순차적으로 접근하는 데이터에 적합하다. 예 링크드 리스트, 테이프 드라이브 등

단점

  • 다른 장치에 비해 더 많은 공간을 필요로 함 정렬 기술입니다.
  • 비교적 덜 효율적입니다.

빠른 정렬

빠른 정렬은 다시 분할 정복 방법을 사용하여 목록의 요소를 정렬합니다. 또는 배열. 피벗 요소를 대상으로 지정하고 선택한 피벗 요소에 따라 요소를 정렬합니다.

예를 들어

  • 요소가 " 1인 배열이 제공됩니다. ,8,3,9,4,5,7 ”.
  • " 7 "을 파일럿 요소로 가정합니다.
  • 이제 다음과 같은 방식으로 어레이를 분할합니다. 왼쪽에는 피벗 요소 " 7 "보다 작은 요소가 포함되고 오른쪽에는 피벗 요소 " 7 "보다 큰 요소가 포함됩니다.
  • 이제 두 개의 배열 " 1,3,4,5가 있습니다. ” 및 “ 8, 9 ”.
  • 다시, 위에서 했던 것과 동일하게 두 배열을 나누어야 합니다. 유일한 차이점은 피벗 요소가 변경된다는 것입니다.
  • 배열에서 단일 요소를 얻을 때까지 배열을 분할해야 합니다.
  • 마지막에 모든 피벗 요소를 왼쪽에서 오른쪽으로 순서를 지정하면 정렬됩니다.array.

빠른 정렬 프로그램 

``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] = pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest  highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ```

출력

퀵 정렬의 시간 복잡도

  • 최악의 경우: 퀵 정렬의 최악의 시간 복잡도는 O( n 2).
  • 평균 사례: 퀵 정렬의 평균 시간 복잡도는 O( n log( n ) ).
  • 가장 좋은 경우: 퀵 정렬의 가장 좋은 시간 복잡도는 O( n log( n )).

장점

  • Python에서 가장 좋은 정렬 알고리즘으로 알려져 있습니다.
  • 많은 양의 데이터를 처리할 때 유용합니다.
  • 추가 공간이 필요하지 않습니다.

단점

  • 최악의 복잡성은 버블 정렬의 복잡성과 유사하며 삽입 정렬.
  • 이 정렬 방법은 이미 정렬된 목록이 있는 경우 유용하지 않습니다.

힙 정렬

힙 정렬은 이진 검색 트리의 고급 버전입니다. . 힙 정렬에서 배열의 가장 큰 요소는 항상 트리의 루트에 배치된 다음 루트와 리프 노드를 비교합니다.

예:

  • " 40, 100, 30, 50, 10 " 요소를 갖는 배열이 제공됩니다.
  • " 1단계 " 에 따라 트리를 만들었습니다. 배열에 요소의 존재.

  • “ 2단계” 에서 우리는 최대 힙을 만들고 있습니다. 내림차순으로 요소. 가장 큰 요소는맨 위(루트)에 있고 가장 작은 요소가 맨 아래(리프 노드)에 있습니다. 주어진 배열은 “ 100, 50, 30, 40, 10 ”이 됩니다.

  • " 3단계 " 에서 우리는 배열의 최소 요소를 찾을 수 있도록 최소 힙을 만들고 있습니다. 이렇게 하여 최대 요소와 최소 요소를 얻습니다.

  • "4단계" 에서 동일한 단계를 수행하여 정렬된 배열을 얻습니다.

힙 정렬용 프로그램 

``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left  n and arr[ larger_element ]  arr[ left ]: larger_element = left if right  n and arr[ larger_element ]  arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ```

출력

힙 정렬의 시간 복잡도

  • 최악의 경우: 힙 정렬의 최악의 시간 복잡도는 다음과 같습니다. O( n log( n )).
  • 평균 사례: 힙 정렬의 평균 시간 복잡도는 O( n log( n )).
  • 최상의 경우: 힙 정렬의 최적 시간 복잡도는 O( n log( n )).

장점

  • 생산성 때문에 주로 사용된다.
  • in-place 알고리즘으로 구현됩니다.
  • 대용량 저장 공간이 필요하지 않습니다.

단점

  • 저장 공간이 필요합니다.
  • 요소를 정렬하기 위한 트리를 만든다.

정렬기법의 비교

정렬방법 최상의 경우의 시간복잡도 평균의 경우의 시간복잡도 최악의 경우의 시간복잡도 공간복잡도 안정성 에서 -
맨 위로 스크롤