이코테 파이썬 : 정렬 알고리즘 정리

정렬 알고리즘 

 

선택정렬

: 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸는 것을 반복

매번 현재 범위에서 제일 작은 데이터를 골라서 제일 앞쪽으로 보내주는 정렬방법!

step : 처리되지 않은 데이터 中 가장 작은 데이터를 선택하여 가장 앞의 수과 바꿔준다.

step0  : 처리되지 않은 데이터 中 가장 작은 0을 선택하여 가장 앞의 7과 바꿔준다.

이 때 처리 되지 않은 데이터는 데이터 전체 범위를 말함.

 

- 탐색 범위는 매번 줄어든다.

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)

 

💡python의 swap 방법

값을 바꿔주는 방법에서 temp 을 사용하지 않고 바로 바꿔줄 수 있다.

array[i] , array[min_index] = array[min_index] , array[i]

 

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 방식의 정렬 알고리즘이다.

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1,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)

퀵 정렬

array = [5,7,9,0,3,1,6,2,4,8]

# 퀵 정렬은 재귀적인 방식으로 동작!

def quick_sort(array, start,end):

  # 종료 조건
  if start >= end : # 원소가 한개인 경우
    return

  pivot = start
  left = start+1
  right = end

# left와 right가 엇갈린 경우 반복문을 탈출하도록 한다.
  while(left <= right): 
  
  # 왼쪽에서부터 pivot보다 큰 데이터를 찾는다.
    while (left <=end and array[left] <= array[pivot]):
      left +=1 
	
  # 오른쪽에서부터 pivot보다 작은데이터를 찾는다.
    while(right >start and array[right] >= array[pivot]):
      right -=1
  # 만약 두 데이터가 엇갈렸다면 피벗 <-> 작은 데이터
    if left>right:
      array[right] , array[pivot] = array[pivot],array[right]
  # 엇갈리지 않았다면 피벗보다 작은 데이터와 큰 데이터를 교체해준다.
    else : 
      array[left] ,array[right] = array[right] , array[left]
    
  # 피벗보다 작은 데이터에 대해 퀵 정렬
  quick_sort(array,start,right-1)
  # 피벗보다 큰 데이터에 대해 퀵 정렬
  quick_sort(array, right+1,end)

quick_sort(array, 0, len(array)-1)
print(array)

 

파이썬의 장점을 더 살려보자

리스트 슬라이싱과 리스크 컴프리헨션을 이용한다!! 

array = [5,7,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))

---

계수 정렬

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

#정렬할 리스트의 값의 모든 범위를 포함하는 리스트를 선언해준다.
# 모든 값은 0으로 초기화
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[j]):
    print(i,end=' ')

정렬 알고리즘 비교

 

*다만 퀵 정렬은 데이터 정렬 방식에 따라서 최악의 경우 o(N^2)이 나올 수 있음

 

 

* random 한 값을 사용한다.

* 파이썬 기본 : 병합정렬을 기본으로하는 하이브리드 방식을 사용한다. 

---

1️⃣실전 문제 1 : 위에서 아래로 

💡배운 내용 : 파이썬의 sorted

- 파이썬의 기본 정렬 라이브러리 sorted에 대해서 알게되었다.

- 사용법

 

sorted는 첫번째 매개변수로 들어온 이터러블한 데이터를 새로운 정렬된 리스트로 만들어서 반환해주는 함수이다!

 

여기서 이터러블한 데이터는 반복가능한 데이터를 의미한다.

array = sorted(array,reverse=True)

 

- sorted(정렬할 데이터)

list.sort( ) 와의 차이

sort는 리스트에서만 정의된다.  그러나 sorted는 모든 반복가능한 데이터에서 사용가능하다!

 

- sorted(정렬할 데이터 , key= 정렬 기준  )

key는 어떤 기준으로 정렬할 것인지를 나타낸다.

 

- sorted(정렬할 데이터, reverse=오름차순(False) 또는 내림차순(True))

reverse는 오름차순과 내림차순 정렬을 지정하는데 사용한다.

- sorted(정렬할 데이터, key= 정렬 기준 , reverse = 오름차순(False) 또는 내림차순(True) )

n = int(input())

array = []
for i in range(n):
  array.append(int(input()))

array = sorted(array,reverse=True)

for i in array:
  print(i, end=' ')

---

2️⃣실전문제 2 : 성적이 낮은 순서로 학생 출력하기

(이름 성적) 묶음에서 성적으로 정렬을 수행하고 이름을 출력해야한다. 

n = int(input())

array = []
for i in range(n):
  input_data = input().split()
  array.append((input_data[0],int(input_data[1])))

print(array)

array = sorted(array,key= lambda student : student[1])

for student in array:
  print(student[0], end=' ')

람다를 사용한 경우 결과

😭람다문법 어떻게 쓰는거야?!?

우선 람다를 사용하지 않고 코드를 풀어서 이해해보았다. 

n = int(input())

def get_score(student):
  return student[1]

array = []
for i in range(n):
  input_data = input().split()
  array.append((input_data[0],int(input_data[1])))

print(array)

array = sorted(array,key= get_score)

for student in array:
  print(student[0], end=' ')

 

 

람다를 사용하지 않은 경우 결과

💡sorted에서 key에 따라 정렬되는 원리를 알아보자!

key를 지정하지 않으면 

학생 리스트 [ (이름1, 80), (이름2, 90), (이름3, 75) ]을 비교해서 정렬하게 된다.

튜플끼리의 비교는 첫번째 원소부터 순서대로 비교하므로 이름 순으로 정렬된다.

 

그러나 key함수를 지정하면 각 원소에 대해 key에 지정한 lambda x:x[1] 함수를 호출하고 그 결과값으로 정렬을 수행한다.

 

* (이름1, 80)에 대해서는 80을 반환

* (이름2, 90)에 대해서는 90을 반환

* (이름3, 75)에 대해서는 75를 반환

 

따라서 sorted는 80,90,75 값을 기준으로 정렬을 수행하게 된다!

 

💡람다를 적용해보자

array = sorted(array,key= lambda student : student[1])

 

array에 대해서 첫번째 원소부터 람다의 매개변수인 student에 들어가서 student[1]이라는 값으로 반환된다.

따라서 (이름1, 80)인 첫번째 원소가 람다함수에 들어가면  stduent[1]인 80이 반환되는 것이다

 

결과적으로  아래와 같이 값을 반환하게 된다

* (이름1, 80)에 대해서는 80을 반환

* (이름2, 90)에 대해서는 90을 반환

* (이름3, 75)에 대해서는 75를 반환

---

3️⃣실전 문제 3 : 두 배열의 원소 교체

 

n,k = map(int,input().split())
A = []
B = []
A  = list(map(int, input().split()))
B  = list(map(int, input().split()))

A.sort()
B.sort(reverse=True)

for i in range(k):

  if A[i]<B[i]:
    A[i], B[i] = B[i], A[i]
  else:
    continue

print(sum(A))

 

💡python의 continue와 break의 차이 

python에서 continue와 break의 차이를 정리하자

나는 A의 원소보다 B의 원소가 클 때만 서로 원소를 교체하도록 하였고, 아닐 경우에는 다음 for문 반복으로 넘어간다는  목적으로 continue를 사용하였다.

 

continue : 반복문 안에서 현재 반복을 건너뛰고 다음 반복으로 넘어간다.

for i in range(5):
    if i == 2:
        continue
    print(i)

 

i가 2인 경우 continue를 만나면 그 반복은 건너뛰고 다음 반복으로 넘어가게 된다.

따라서 출력 결과는 0 1 3 4 가 된다.

 

break : 반복문 전체를 완전히 빠져나온다! 

for i in range(5):
    if i == 2:
        break
    print(i)

 

i가 2인 경우 break를 만나고, 반복문 전체를 완전히 빠져나오게 된다. 

따라서 출력결과는 0 1 이 된다.

 

우선, A의 원소보다 B의 원소가 작을 때는 교체를 하지 않고 다음 반복으로 넘어간다는 목적에서 continue를 사용한 것은 적절하였다.

 

하지만 A는 오름차순 정렬, B는 내림차순 정렬이 된 상태이다. 

따라서 만약 특정 i 인덱스에서 A가 B보다 컸을 경우 B의 이후 원소도 A의 원소보다 작을 것이다!!

 

따라서 더이상 반복문을 수행할 필요가 없고 break문을 사용하는 것이 더 적절하다.

 

수정한 코드

n,k = map(int,input().split())
A = []
B = []
A  = list(map(int, input().split()))
B  = list(map(int, input().split()))

A.sort()
B.sort(reverse=True)

for i in range(k):

  if A[i]<B[i]:
    A[i], B[i] = B[i], A[i]
  else:
    break

print(sum(A))

 

생각 과정 

 

 

위 사진은 문제를 풀기 전 생각 과정을 적어본 내용이다.

 

- 생각 1 의 경우가 이 문제를 푼 원리였다.

- 생각 2 는 A와 B의 값들이 나오는 개수를 파악하여 계수 정렬로 풀 수 있을까? 하는 생각이었다.

그러나 사용자 입력에 따라 값의 범위가 결정된다는 점에서 값 범위를 예측할 수 없어 사용할 수 없다고 판단하였다.