코딩 테스트/정렬11 위에서 아래로 p. 178 import sys input=sys.stdin.readline N=int(input()) num=[] for i in range(N): num.append(int(input())) num.sort(reverse=True) for i in range(N): print(num[i], end=' ') 2021. 2. 11. 계수 정렬 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있는 알고리즘 매우 빠르다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적 모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언해야한다. ex) 가장 작은 데이터가 0, 가장 큰 데이터가 1,000,000이면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트 선언 앞 3가지의 정렬 알고리즘처럼 비교하는 비교 기반의 정렬 알고리즘이 아니다. [과정] 데이터 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 리스트 내의 값들을 0으로 초기화 한다. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 가장 앞에 있는 데이터부터 해당 데이터 값의 리스트 값을 +1한다. .. 2021. 2. 8. 퀵 정렬 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼 후 리스트를 반으로 나눈다. pivot을 어떻게 설정하냐에 따라 여러 가지 방식으로 퀵 정렬을 구분한다. 다음에서 나올 퀵 정렬은 호어 분할 방식을 사용한다. 호어 분할 방식에서 pivot은 리스트에서 첫번째 데이터로 사용한다. 리스트의 왼쪽에서부터 pivot보다 큰 데이터를 찾고 리스트의 오른쪽에서부터 pivot보다 작은 데이터를 찾는다. 그 다음, 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 만약 큰 데이터의 인덱스와 작은 데이터의 인덱스가 엇갈릴 경우, 작은 데이터와 pivot의 위치를 바꾼다. [과정] 다음과 같이 초기 데이터가 구성되어 있다고 가정한다. pivot = '5' 왼쪽에서부터 pivot보다 .. 2021. 2. 8. 삽입 정렬 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입 삽입정렬은 필요할 때만 위치를 바꿈 -> 데이터가 거의 정렬되어 있을 때 효율적 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터들은 이미 정렬되어 있다고 가정함 정렬이 이루어진 원소는 항상 오름차순을 유지 삽입될 데이터보다 작은 데이터를 만나거나 앞에 더이상 데이터가 없으면, 그 위치에서 멈춤 [과정] 첫 데이터 '5'는 정렬되어있다고 판단하고, 두번째 데이터가 어디 들어갈지 찾는다. 두번째 데이터 '1'은 '5'의 왼쪽으로 들어가거나, 오른쪽으로 들어가는 두 경우만 존재한다. 오름차순으로 정렬한다고 했을때, '1'은 '5'보다 작고 '5'의 앞에 더이상 데이터가 없으므로, '1'은 '5'의 왼쪽에 삽입한다. 이어서 '4'가 어디.. 2021. 2. 5. 선택 정렬 매번 가장 작은 것을 선택하여 차례대로 바꿈 [과정] 데이터의 개수 = 6 현재 정렬되지 않은 데이터 중 가장 작은 데이터 = 회색 이미 정렬된 데이터 = 하늘색 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 가장 작은 데이터를 선택한다. 가장 작은 데이터 '0'을 선택해 맨 앞에 있는 데이터 '5'와 자리를 바꾼다. 정렬되어 있지 않은 데이터 중 가장 작은 데이터 '1'을 선택한다. '1'이 현재 있는 자리는 정렬되어 있지 않은 데이터 중 가장 앞자리이므로 그대로 둔다. 정렬되어 있지 않은 데이터 중 가장 작은 데이터 '2'를 선택한다. 정렬되어 있지 않은 데이터 중 가장 앞자리에 있는 '4'의 자리에 '2'를 둔다. 그 후 정렬되어 있지 않은 데이터 중 가장 작은 데이터 '3'을 선택한다. .. 2021. 2. 5. 이전 1 2 다음
