정렬이란 무엇입니까?

정렬은 데이터 항목 간의 선형 관계를 기반으로 특정 순서(일반적으로 오름차순 또는 내림차순)로 데이터를 정렬하는 프로세스를 의미합니다.

정렬이 필요한 이유는 무엇입니까?

정렬은 효율적인 데이터 검색을 가능하게 하고 데이터 분석을 단순화하며 전반적인 데이터 관리를 향상시키므로 구조화된 데이터로 작업할 때 매우 중요합니다.

정렬 알고리즘

이 게시물에서는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 빠른 정렬 등의 정렬 알고리즘을 다룹니다.

버블정렬

버블 정렬은 배열을 반복적으로 진행하면서 인접한 요소를 비교하고 순서가 잘못된 경우 교체합니다. 이 프로세스는 배열이 정렬될 때까지 계속되며 더 큰 요소가 끝까지 "버블링"됩니다.

연산

1단계: 시작
2단계: i = 0
3단계: i 4단계: j = 0
5단계: j 6단계: array[j] > array[j 1]인 경우 7단계로 이동합니다. 그렇지 않으면 8단계로 이동
7단계: 배열[j]와 배열[j 1]
바꾸기 8단계: j를 증가시킵니다. 5단계로 이동
9단계: i를 증가시킵니다. 3단계로 이동
10단계: 종료

암호

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j 1]:
                arr[j], arr[j 1] = arr[j 1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

시간 복잡도

최상의 사례 : O(n)
평균 사례 : O(n^2)
최악의 경우 : O(n^2)

선택 정렬

선택 정렬은 배열의 정렬되지 않은 부분에서 가장 작은 값을 찾아 해당 부분의 시작 부분에 배치합니다.

연산

1단계: 시작
2단계: i = 0
3단계: i 4단계: 최소값 = i; j = 나는 1
5단계: j 6단계: array[minimum_value] > array[j]인 경우 7단계로 이동합니다. 그렇지 않으면 8단계로 이동
7단계: 최소값 = j
8단계: j를 증가시킵니다. 5단계로 이동
9단계: 배열[최소_값]과 배열[i]
교체 10단계: i를 증가시킨다. 3단계로 이동
11단계: 종료

암호

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i   1, len(arr)):
            if arr[j] 




  
  
  시간 복잡도


최상의 경우 : O(n^2)

평균 사례 : O(n^2)

최악의 경우 : O(n^2) 


  
  
  삽입 정렬


삽입 정렬은 정렬되지 않은 부분에서 각 요소를 가져와서 정렬된 부분의 올바른 위치에 삽입하여 한 번에 한 요소씩 정렬된 배열을 만듭니다.


  
  
  연산


1단계: 시작

2단계: i = 1

3단계: i 
4단계: 키 = arr[i]

5단계: j = i - 1

6단계: j >= 0이고 arr[j] > 키이면 7단계로 이동합니다. 그렇지 않으면 10단계로 이동

7단계: arr[j 1] = arr[j]

8단계: j를 1만큼 감소

9단계: 6단계로 이동

10단계: arr[j 1] = 키

11단계: i를 1씩 증가시킵니다. 3단계로 이동

12단계: 종료


  
  
  암호




def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j   1] = arr[j]
            j -= 1

        arr[j   1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)





  
  
  시간 복잡도


최상의 사례 : O(n)

평균 사례 : O(n^2)

최악의 경우 : O(n^2) 


  
  
  병합 정렬


병합 정렬은 배열을 더 작은 하위 배열로 재귀적으로 나누고 정렬한 다음 다시 병합하는 분할 정복 알고리즘입니다.


  
  
  연산


병합 정렬 알고리즘


1단계: 시작

2단계: length(array) 
3단계: mid_point = length(array) // 2

4단계: left_half = 배열[:mid_point]

5단계: right_half = 배열[mid_point:]

6단계: sorted_left = merge_sort(left_half)

7단계: sorted_right = merge_sort(right_half)

8단계: 병합 반환(sorted_left, sorted_right)

9단계: 종료

병합 기능


1단계: 시작

2단계: sorted_merge = []

3단계: l = 0, r = 0

4단계: l 
5단계: 왼쪽[l] 
6단계: sorted_merge에 left[l]를 추가합니다. l을 1씩 증가

7단계: sorted_merge에 right[r]를 추가합니다. r을 1씩 증가시킵니다.

8단계: 4단계로 이동

9단계: l 
10단계: sorted_merge에 left[l]을 추가합니다. l을 1씩 증가 

11단계: 9단계로 이동

12단계: r 
13단계: sorted_merge에 right[r]를 추가합니다. r을 1씩 증가시킵니다.

14단계: 12단계로 이동

15단계: sorted_merge
 반환
16단계: 종료


  
  
  암호




def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 




  
  
  시간 복잡도


최상의 사례 : O(n log n)

평균 사례 : O(n log n)

최악의 경우 : O(n log n) 


  
  
  빠른 정렬


빠른 정렬은 분할 정복 접근 방식을 사용하는 효율적인 내부 정렬 알고리즘입니다. 피벗 요소를 선택하고 피벗보다 작은 요소는 왼쪽에 있고 피벗보다 큰 요소는 오른쪽에 있도록 피벗 주위의 배열을 분할합니다. 그런 다음 이 프로세스는 하위 배열에 재귀적으로 적용됩니다.


  
  
  연산


빠른 정렬


1단계: 시작

2단계: 낮음 
3단계: 피벗_인덱스 = 파티션(arr, low, high)

4단계: 빠른 정렬(arr, low,ivot_index - 1)

5단계: 빠른 정렬(arr,ivot_index 1, high)

6단계: 종료 

파티션 기능


1단계: 시작

2단계: 피벗 = arr[높음]

3단계: 왼쪽 = 낮음, 오른쪽 = 높음 - 1

4단계: 왼쪽 
5단계: arr[왼쪽] > 피벗 및 arr[오른쪽] 를 바꿉니다.
6단계: arr[left] 
7단계: arr[right] >= 피벗인 경우 오른쪽 감소

8단계: 4단계로 이동

9단계: arr[left]와 arr[high]
 교체
10단계: 왼쪽으로 돌아가기

11단계: 종료 


  
  
  암호




def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 




  
  
  시간 복잡도


최상의 사례 : O(n log n)

평균 사례 : O(n log n)

최악의 경우 : O(n^2)