- 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
-
버블 정렬 : 매번 연속된 두개의 인덱스를 비교해, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법.
-
선택 정렬 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복함.
-
퀵 정렬 : 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식 동작, 가장 많이 사용되는 빠른 알고리즘
-
힙 정렬 : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조인 힙을 바탕으로, 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨.
-
병합정렬 : 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
(분할 정복(divide and conquer) 방법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략) -
삽입 정렬 : 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입, 데이터가 거의 정렬되어 있을 때 훨씬 효율적임.
-
쉘 정렬 : 삽입 정렬이 거의 정렬된 배열에서 최적의 성능을 내는 것에서 착안한 정렬 방법, 삽입 정렬을 띄엄띄엄한 간격으로 먼저 수행하고, 그 간격을 점차 좁혀나가면서 최종적으로는 거의 정렬된 배열을 삽입 정렬로 마무리함.
-
계수 정렬 : '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때'만 사용할 수 있지만, 매우 빠른 정렬 알고리즘
-
파이썬 정렬 라이브러리 - 기본 정렬 라이브러리 sorted() 함수
위에서 아래로
문제
하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다.
입력
첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1 <= N <= 500
둘째 줄부터 N + 1 번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하 자연수
출력
입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분해서 출력하면된다. 동일한 수는 순서상관없다.
입력 예시
3
15
27
12
출력 예시
27 25 12
풀이
기본 라이브러리 : sorted() 활용
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='')성적이 낮은 순서로 학생 출력하기
문제
N명의 학생의 성적 정보가 주어진다. 형식은 이름 성적 으로 주어지는데 이때 이들의 성적이 낮은 순으로 학생 이름을 출력하는 문제다.
입력
첫 번째 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)
두 번째 줄 부터 N+1 번째 줄 까지 학생의 이름 그리고 성적이 공백으로 주어진다. 학생이름 길이는 100이하, 성적은 100이하 자연수로 주어진다.
출력
모든 학생의 이름을 성적이 낮은 순으로 출력하면된다. 동일한 성적은 자유롭게 출력하면된다.
입력 예시
2
홍길동 96
이순신 78
출력 예시
이순신 홍길동
풀이
계수정렬 : 입력되는 데이터는 학생의 이름과 점수지만, 출력할 때는 학생의 이름만 출력하면 되므로, 학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행
n = int(input())
array = []
for i in range(n):
input_data = input().split()
# 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
array.append((input_data[0], int(input_data[1])))
array = sorted(array, key=lambda student: student[1])
for student in array:
print(student[0], end=' ')