📘선택 정렬 (Selection Sort)

선택 정렬은 배열에서 가장 작은 요소를 선택해서 맨 앞으로 보내는 과정을 반복하여 전체 리스트를 정렬하는 방식이다. 이 방법은 이해하기 쉽고 구현하기도 간단하지만, 데이터의 양이 많을 때는 비효율적일 수 있다.

선택 정렬 특징

• 시간 복잡도는 O(n^2)이다.
• 구현이 간단하다는 장점이 있지만 비교적 느린 정렬 방법으로 대용량 데이터에는 적합하지 않다.
• 데이터가 적을 때나 구현의 단순성을 우선시할 때 유용하게 사용될 수 있다.

선택 정렬 과정

• 배열 전체를 순회하면서 가장 작은 값을 찾는다. 이 최소값은 배열의 첫 번째 위치와 교환된다.
• 배열의 첫 번째 요소를 제외한 나머지 부분에서 다음으로 작은 값을 찾는다. 이 값을 배열의 두 번째 위치와 교화한다.
• 이 과정을 배열의 각 위치에 대해 반복하며, 각 단계에서 하나의 위치가 정렬된다.

lst = [4,7,1,3,5]

for i in range(len(lst)-1):
    for j in range(i+1,len(lst)):
        if lst[i] > lst[j]:
            lst[i], lst[j] = lst[j], lst[i] 

print(*lst)

정렬 전
=> [4, 7, 1, 3, 5]

i=0

• j=2 i번째 원소 4와 j번째 원소 1 교환 => [1, 7, 4, 3, 5]

i=1

• j=2 i번째 원소 7과 j번째 원소 4 교환 => [1, 4, 7, 3, 5]
• j=3 i번째 원소 4와 j번째 원소 3 교환 => [1, 3, 7, 4, 5]

i=2

• j=3 i번째 원소 7과 j번째 원소 4 교환 => [1, 3, 4, 7, 5]

i=3

• i=3, j=4 i번째 원소 7과 j번째 원소 5 교환 => [1, 3, 4, 5, 7]

결과

• 최종적으로 정렬된 상태 =>[1, 3, 4, 5, 7]

📘삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬된 부분 리스트에 현재 요소를 적절한 위치에 삽입하는 방식으로 배열 또는 리스트를 정렬하는 알고리즘이다. 삽입 정렬은 일상 생활에서 카드 게임을 정렬할 때와 유사하게 작동하며, 비교적 이해하기 쉽고 구현도 간단하다.

삽입 정렬 특징

• 시간 복잡도는 평균적으로 O(n^2)이다. 최악의 경우 모든 내부 요소들이 비교되고 이동해야 하기 때문이다. 하지만 이미 정렬된 데이터에 대해서는 O(n)으로 빠르게 작동할 수 있다.
• 작은 데이터셋 또는 거의 정렬된 데이터에 대해 매우 효율적이다.
• 구현이 간단하여 코드가 짧을 때 유용하게 사용될 수 있다.

삽입 정렬 과정

• 배열의 첫 번째 요소는 이미 정렬된 것으로 간주한다. 그리고 두 번째 요소부터 마지막 요소까지 차례대로 정렬된 부분에 삽입한다.
• 각 단계에서 현재 요소를 취하고, 이미 정렬된 부분 리스트에서 이 요소보다 큰 모든 요소를 오른쪽으로 한 칸씩 이동시킨다. 이 과정은 현재 요소가 들어갈 올바른 위치를 만들기 위해 수행된다.
• 적절한 위치가 확보되면 현재 요소를 그 자리에 삽입한다.
• 배열의 모든 요소가 정렬될 때까지 이 과정을 반복한다.

lst = [4,7,1,3,5]

for i in range(1,len(lst)):
    for j in range(i,0,-1): # 뒤에서부터 앞으로 가면서
        if lst[j-1] > lst[j]: # 앞의 값 vs 현재 비교
            lst[j], lst[j-1] = lst[j-1], lst[j]
        else:
            break
print(*lst)

정렬 전
=> [4, 7, 1, 3, 5]

i=2

• j=2 현재 원소 1과 앞의 원소 7 교환 => [4, 1, 7, 3, 5]
• i=2, j=1 현재 원소 1과 앞의 원소 4 교환 => [1, 4, 7, 3, 5]

i=3

• j=3 현재 원소 3과 앞의 원소 7 교환 => [1, 4, 3, 7, 5]
• i=3, j=2 현재 원소 3과 앞의 원소 4 교환 => [1, 3, 4, 7, 5]

i=4

• j=4 현재 원소 5와 앞의 원소 7 교환 => [1, 3, 4, 5, 7]

결과

• 최종적으로 정렬된 상태 => [1, 3, 4, 5, 7]

📘버블 정렬 (Bubble Sort)

버블 정렬은 매우 직관적인 정렬 방식으로, 인접한 두 요소를 비교하고 필요한 경우 위치를 교환하여 전체 리스트를 정렬하는 알고리즘이다. 이 정렬 방법은 그 과정이 마치 "거품이 물 속에서 상승하는 것처럼 보인다"하여 붙여진 이름이다.

버블 정렬 특징

• 시간 복잡도는 평균적으로 O(n^2)이다.
• 큰 데이터셋에 대해서는 매우 비효율적일 수 있다.
• 데이터가 이미 거의 정렬된 상태라면 매우 빠르게 동작할 수 있다.

버블 정렬 과정

• 배열의 처음부터 시작하여 바로 뒤에 있는 요소와 비교한다. 만약 앞의 요소가 뒤이 요소보다 크다면 두 요소의 위치를 교환한다. 이 과정은 배열의 끝까지 진행된다.
• 배열의 시작점으로 돌아가서 다시 비교를 시작한다. 이때, 이전 패스에서 가장 큰 요소가 배열의 끝으로 이동했기 때문에, 마지막 요소는 다음 비교에서 제외된다.
• 더 이상 교환이 필요 없을 때까지, 즉 전체 배열이 정렬될 때까지 이 과정을 반복한다. 각 반복마다 검사해야 할 요소의 수가 하나씩 줄어든다.

lst = [4,7,1,3,5]

for i in range(len(lst)-1, 0, -1):
    for j in range(i):
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]

print(*lst)

정렬 전
=> [4, 7, 1, 3, 5]

i=4

• j=1 현재 원소 7과 뒤의 원소 1 위치 교환 => [4, 1, 7, 3, 5]
• j=2 현재 원소 7과 뒤의 원소 3 위치 교환 => [4, 1, 3, 7, 5]
• j=3 현재 원소 7과 뒤의 원소 5 위치 교환 => [4, 1, 3, 5, 7]

i=3

• j=0 현재 원소 4와 뒤의 원소 1 위치 교환 => [1, 4, 3, 5, 7]
• j=1 현재 원소 4와 뒤의 원소 3 위치 교환 => [1, 3, 4, 5, 7]

결과

• 최종적으로 정렬된 상태 => [1, 3, 4, 5, 7]