이코테 | 정렬

정렬

: 데이터를 특정 기준에 따라 순서대로 나열하는 것

 

선택 정렬

: 가장 작은 것을 선택하는 방법,

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,

그다음 작은 데이터를 두 번째 데이터와 바꾸는 과정을 반복

 

시간 복잡도 : O(N^2)

-> 데이터의 개수가 커지면 커질 수록 수행 속도가 급격히 느려짐, 비효율적

 

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[j]<array[min_index]:
            min_index = j
    
    array[i], array[min_index] = array[min_index], array[i]	#스와프
    
print(array)

 

파이썬 스와프 예제 코드

array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)
#출력 : [5, 3]

파이썬 스와프 코드를 이용하면 간단하게 값을 교체할 수 있다.

 

---

삽입 정렬

: 특정한 데이터를 적절한 위치에 삽입하는 방식 (두 번째 데이터부터 시작)

 

시간 복잡도 : O(N^2)

-> 데이터의 개수가 커지면 커질 수록 수행 속도가 급격히 느려짐, 비효율적

-> 리스트의 데이터가 거의 정렬되어 있는 상태일 경우 매우 빠르게 동작하여 O(N)의 시간 복잡도를 가질 수 있다.

-> 정렬되어 있는 데이터가 입력으로 주어지는 문제라면 퀵 정렬보다 삽입 정렬이 더 좋음!

 

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):    #i부터 1까지 1씩 감소하면서 반복
        if array[j]<array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
       
print(array)

 

1) i=1, j=1

array[1] = 5, array[0] = 7

array[1]<array[0]이므로 array[1], array[0] 값 교체

[5, 7, ~ ]

 

2) i=2, j=2

array[2] = 9, array[1] = 7

break

 

3) i=3, j=3

array[3] = 0, array[2] = 9 -> 값 교체

[5, 7, 0, 9 ~ ]

 

4) i=3, j=2

array[2] = 0, array[1] = 7 -> 값 교체

[5, 0, 7, 9 ~]

 

5) i=3, j=1

array[1] = 0, array[0] = 5 -> 값 교체

[0, 5, 7, 9 ~]

 

 

---

퀵 정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터, 작은 데이터의 위치를 바꾼다.

 

피벗 : 큰 데이터, 작은 데이터를 교환하기 위한 기준 (첫 번째 데이터를 피벗으로 정한다.)

시간 복잡도 : O(NlogN)

 

* 퀵 정렬 소스코드

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

def quick_sort(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)

*

 

quick_sort(array, start, right-1) : start부터 피벗 전까지 퀵정렬 재수행
quick_sort(array, right+1, end) : 피벗 다음부터 end까지 퀵정렬 재수행

 

 

* 파이썬 장점을 살린 퀵 정렬 소스코드

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

 

---

계수 정렬

: 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 방법,

  특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

 

시간 복잡도 : O(N+K) (데이터 개수 N, 최댓값 K)

 

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.

데이터 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을 수록 유리하다.

가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

-> 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 함

 

ex) 0이상 100이하인 성적 데이터 정렬하는 경우, (100+1개의 수가 존재)

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0]*(max(array)+1)  #가장 큰 수+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=' ')

 

 

---

파이썬 정렬 라이브러리

sorted()

 

시간 복잡도 : O(NlogN)

 

1) sorted()

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array)
print(result)

 

2) sort() - array 변수에서 바로 정렬할 수 있음

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()
print(array)

 

3) key 활용

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)

key 매개변수를 입력으로 받을 수 있음, key 값에는 함수가 들어가야 함(정렬 기준)

 

 

---

 

위에서 아래로

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다.

이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

 

첫 번째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1<=N<=500)

두 번째 줄부터 N+1 번째 줄까지 N개의 수가 입력된다. 수의 범위는 1이상 100,000 이하의 자연수

 

Tip!

- 모든 수는 1이상 100,000 이하이므로 모든 정렬 알고리즘을 사용할 수 있다.

(그 중 간편한 라이브러리 사용!)

n = int(input())
array = []

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

array.sort(reverse=True)

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

 

---

성적이 낮은 순서로 학생 출력하기

 

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다.

각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

(성적이 낮은 순서대로 이름을 출력, 성적이 동일한 학생들의 순서는 자유롭게 출력)

 

첫 번째줄에 학생 수 N이 입력된다. (1<=N<=100,000)

두 번째 줄부터 N+1 번째 줄에는 학생의 이름을 나타내는 문자열 A, 학생의 성적을 나타내는 정수 B가

공백으로 구분되어 입력된다. A의 길이, B는 100이하의 자연수이다.

 

Tip!

- 100,000 이하의 학생 수가 입력되므로 일반 라이브러리 사용

- 튜플, key 활용

 

1) def 함수 활용

n = int(input())
array = []

def setting(data):
    return data[1]
    
for i in range(n):
    a, b = map(str, input().split())
    array.append((a, int(b)))

array = sorted(array, key=setting)

for i in array:
    print(i[0], end=" ")

 

2) 람다함수 활용

n = int(input())
array = []


for i in range(n):
    a, b = map(str, input().split())
    array.append((a, int(b)))

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

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

 

lamda 매개변수 : 표현식

array의 각 항목을 받아 ('이름', 점수) 그 항목의 두 번째 원소인 점수를 기준으로 정렬한다.

 

---

두 배열의 원소 교체

두 개의 배열 A, B는 N개의 원소로 구성되어 있으며 원소는 모두 자연수이다.

최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소

하나를 골라 서로 바꾸는 것을 말한다.

최대 K번의 바꿔치기 연산을 수행하여 배열 A의 모든 원소의 합이 최대가 되도록 하는 프로그램을 작성하시오.

 

첫 번째 줄에 N, K가 공백으로 구분되어 입려괴나 (1<=N<=100,000, 0<=K<=N)

두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. (모든 원소는 10,000,000보다 작은 자연수)

세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. (모든 원소는 10,000,000보다 작은 자연수)

 

n,k = map(int, input().split())
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] # a에서 가장 작은 수와 b에서 가장 큰 수 스와핑
    else:
        break
    
print(sum(a))

 

 

---

 

수 정렬하기

 

백준_2750

백준_2751

 

import sys
input=sys.stdin.readline

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

array.sort()
for i in array:
    print(i)

 

같은 문제이지만 2750번 문제는 입력받는 개수가 1,000개로 제한되어 있어 어떤 정렬이던 상관 없다.

하지만 2751번 문제는 100,000,000개까지 입력받을 수 있기 때문에

import sys

input = sys.stdin.readlin을 작성해 준다.

 

 

---

세 수

백준_10817

import sys
input=sys.stdin.readline

a,b,c = map(int, input().split())
array = [a,b,c]
array.sort(reverse=True)
print(array[1])

 

---

ATM

백준_11399

import sys
input = sys.stdin.readline

n = int(input())
array = list(map(int, input().split()))
array.sort()

total = 0
for i in range(n):
    for j in range(0, i+1):
        total += array[j]

print(total)