백준 2750 [파이썬] (len,버블,삽입)

#1 버블정렬

 

n=int(input())

numbers = []
for _ in range(n):
    numbers.append(int(input()))

for i in range(len(numbers)) :
    for j in range(len(numbers)):
        if numbers[i] < numbers[j]:
            numbers[i], numbers[j] = numbers[j], numbers[i]

for n in numbers:
    print(n)

 

1. n으로 정렬하고 싶은 숫자의 개수를 입력받는다.

2. n번 동안 해당 숫자들을 numbers라는 리스트에 append한다.

3. 인접한 두 개의 원소를 비교하는 버블정렬을 통해 크기에 따라 위치를 서로 바꿔준다.

 

 

#2 삽입정렬

 

n=int(input())

numbers = []

for _ in range(n):
    numbers.append(int(input()))

for i in range(1, len(numbers)):
    for j in range(i, 0, -1):  # 인덱스 i부터 1까지 1씩 감소하며 반복
        if numbers[j] < numbers[j - 1]:  # 한 칸씩 왼쪽으로 이동
            numbers[j], numbers[j - 1] = numbers[j - 1], numbers[j]
        else:  # 앞쪽은 이미 정렬이 되어있기 때문에 자기보다 작은 데이터 만나면 그자리에서 멈춤
            break

for i in range(len(numbers)):
    print(numbers[i])

 

---

len()

반복 가능한 객체의 길이를 구하는 가장 일반적인 방법은 len()함수를 이용하는 것입니다.

len을 사용하면 리스트에 들어있는 요소가 총 몇개인지 알 수 있습니다.

count를 사용하면 리스트에 들어있는 요소 중 특정 요소가 몇개인지 알 수 있습니다.

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

print(len(i)) #리스트의 총 개수
#18

print(i.count(7)) #7이 몇개인지 알 수 있음
#5

 

버블 정렬 알고리즘

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

- 인접한 2개의 레코드끼리 비교하여 순서에 맞지 않으면 서로 교환한다.

 

장점

- 구현이 간단하고, 소스코드가 직관적이다.

- 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다

단점

- 시간복잡도가 최선,평균,최악 모두 O(n^2)으로 비효율적이다.

- 정렬되어 있지 않는 원소가 알맞은 위치로 가기 위해 교환 연산이 많이 일어나게 된다.

 

 

삽입 정렬 알고리즘

모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘

- 두 번째 자료부터 시작해서 앞(왼쪽)의 자료와 비교하여 삽입할 위치를 지정한다.

 (2번째 자료는 1번째 자료와 비교, 4번째 자료는 1번째,2번째,3번째 자료와 비교후 삽입될 위치를 찾는 것)

- 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입한다.

 

장점

- 알고리즘이 단순하다.

- 대부분의 원소가 이미 정렬되어 있는 경우, 효율적일 수 있다.

- 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다.

단점

- 평균과 최악의 시간 복잡도가 O(n^2)로 비효율적이다. (최선의 경우는 O(n)임.)

- 버블정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적이다.

 

 

선택 정렬 알고리즘

최솟값을 찾아 앞쪽으로 이동하기를 배열 크기만큼 반복하는 정렬 방법

- 주어진 배열 중에서 최솟값을 찾는다.

- 그 값을 맨 앞에 위치한 값과 교체한다.

 

장점

- 자료 이동 횟수가 미리 결정된다.

단점

- 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있다.

 

 

스와프

파이썬의 리스트 요소 위치를 변경하는 간단한 방법

array = [1,2,3,4,5]
#스와프
array[0], array[3] = array[3], array[0]

print(array) #[4,2,3,1,5]