✏️ 배열이란?
✏️ 정렬(sort)

✏️ 배열이란?

• 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조

배열의 필요성

• 프로그램 내에서 여러 개의 변수가 필요할 때, 하나씩 변수명을 이용하여 접근하는것은 아주아주 비효율적인 방법이다.
• 배열을 사용하면 하나의 선언을 통해서 둘 이상의 변수를 선언할 수 있다.
• 또한 index를 활용하여 특정 변수에 접근할 수 있다는 장점이 있다.

✏️ 정렬(sort)

대표적인 sort 종류

• 버블 정렬(Bubble Sort)
• 카운팅 정렬(Counting Sort)
• 선택 정렬(Selection Sort)
• 퀵 정렬(Quick Sort)
• 삽입 정렬(insertion Sort)
• 병합 정렬(Merge Sort)

🧋Bubble Sort

인접한 두 개의 원소를 비교하여 자리를 계속 교환하는 방식

• 정렬 과정
  1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막자리까지 이동
  2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다
  3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 해서 버블 정렬이라 한다

• 시간 복잡도
  • O(n^2)

• Bubble sort (코드 구현)

def BubbleSort(a,N):
	for i in range(N-1, 0, -1):
    	for j in range(0,i):
        	if a[j] > a[j+1]:
            	a[j], a[j+1] = a[j+1], a[j]

🔢 Counting Sort

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하며, 선형 간에 정렬하는 효율적인 알고리즘

• 제한 사항
  • 정수나 정수로 표현될 수 있는 자료에 대해서만 적용 가능
  • 각 항목의 발생 횟수를 기록 하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문
  • 카운트 들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 점수를 알아야 한다.
• 시간 복잡도
  • O(n + k) : n은 리스트 길이, k는 정수의 최대값

• Counting sort(코드 구현)

def Counting_Srot(A, B, k)
# A [] -- 입력 배열(1 to k)
# B [] -- 정렬된 배열,
# C [] -- 카운트 배열,

	C = [0] * (k+1)
    
    for i in range(0, len(A)):
    	C[A[i]] += 1
    for i in range(1, len(C)):
    	C[i] += C[i-1]
    for i in range(len(B)-1, -1, -1):
    	C[A[i]] -= 1
        B[C[A[i]]] = A[i]