이코테 CHAPTER 06 정렬 + 실전 문제(위에서 아래로)

기준에 따라 데이터를 정렬

• 정렬 Sorting
  • 데이터를 특정한 기준에 따라 순서대로 나열
  • 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘을 공식처럼 사용
• 선택 정렬
  • 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
  • 코드 구현
    • 매번 선형 탐색 → 이중 반복문

    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)
• 삽입 정렬
  • 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
  • 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작
  • 코드 구현

    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
    
    for i in rangedz len(array))：
    	for j in range(i, 0, -1)： # 인덱스 i부터 1 까지 감소하며 반복하는 문법
    		if array[j] < array[j - 1]： # 한 칸씩 왼쪽으로 이동
    			array[j], array[j - 1] = array[j - 1], array[j]
    		else： # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
    			break
    
    print(array)​

  • range의 세 번째 매개 변수
    • range의 매개 변수는 3개(start, end, step)이다.
    • 세 번째 매개 변수인 step에 -1 이 들어가면 start 인덱스부터 시작해서 end + 1 인덱스까지 1 씩 감소한다.
    • 앞의 코드에서는 j 변수가 i부터 1 까지 1 씩 감소한다.
  • 시간 복잡도
    • O(N^2) : 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용
    • 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
      • 최선의 경우 O(N)
      • → 이미 정렬되어 있는 상태애서 다시 삽입 정렬을 수행하는 경우
• 퀵 정렬
  • 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
  • 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
  • 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
  • 가장 기본인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정
  • 시간 복잡도
    • 평균의 경우 O(NlogN)
    • 최악의 경우 O(N^2) → 이미 정렬된 배열에 대해서 퀵 정렬 수행할 때
  • 코드 구현

    array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
    
    def quicksort(array, start, end)：
    	if start >= end： # 원소가 1 개인 경우 종료
    		return
    	pivot = start # 피벗은 첫 번째 원소
    	left = start + 1
    	right = end
    	while left <= right： 
    		# 피벗보다 큰 데이터를 찾을 때까지 반복
    		while left <= end and array [left] <= array [pivot]：
    			left += 1
    		# 피벗보다 작은 데이터를 찾을 때까지 반복
    		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))​

• 계수 정렬
  • 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작
    • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
  • 데이터의 개수가 N, 데이터(양수) 중 최대값이 K일 때 최악의 경우에도 수행 시간 O(N+K) 보장
  • 동작 예시
    • count 하는 방식으로 구현
  • 코드 구현

    # 모든 원소의 값이 0보다 크거나 같다고 가정
    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[i])： 
    		print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력​

  • 복잡도
    • 시간 복잡도와 공간 복잡도: O(N+K)
    • 때에 따라서 심각한 비효율성 초래
      • 데이터가 0과 999,999로 단 2개만 존재하는 경우
    • 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용 가능
      • 성적의 경우 100점을 맞은 학생이 여러명일 수 있기 때문에 계수 정렬이 효과적
• 정렬 알고리즘 비교

 

• 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장

 

 

실전문제

위에서 아래로

• 나의 풀이

  n = int(input())
  
  num_list = [int(input()) for i in range(n)]
  
  #퀵 정렬 이용해보기
  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(" ".join(map(str,quick_sort(num_list))))​

   

마지막에 숫자 리스트를 공백 포함 문자열로 출력하는 걸 못해서 한참 고민했다.

결국 map과 join을 이용해서 한 줄로 코드를 짰지만 왠지 시간이 오래 걸릴 것 같아서..

아래 코드로 다시 짰다.

#파이썬 내장 함수 이용
num_list = sorted(num_list,reverse=True)

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

내장함수와 출력 코드 모두 이전 코드보다 속도가 훨씬 빨라진 것을 확인했다.

 

 

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저