[Data Science] 알고리즘 개념 정리 (정렬 알고리즘 종류)

 

 

 

* 알고리즘 개념 정리 (Algorithm Concepts)

 

- 어떤 문제를 해결하기 위한 자세한 방법을 의미

 

- 좋은 알고리즘은 문제를 더 잘 해결하는 알고리즘입니다.

 

- 컴퓨터 알고리즘 : 컴퓨터가 어떤 문제를 해결하기 위해서 컴퓨터가 이해할 수 있는 방식으로 정리한 해결 방법

 

 

 

-       정렬 알고리즘 : 리스트를 특정 순서대로 정리

 

1>   선택 정렬 (Selection Sort) : 각 위치에 들어갈 값을 탐색하여 정렬

 

인덱스	0	1	2	3	4
리스트 항목	2	5	1	6	9

 

-       0번 인덱스와 1, 2, 3, 4 번 인덱스의 값을 차례대로 비교하여 최소값과 교체한다.

 

인덱스	0	1	2	3	4
리스트 항목	1 (최소값)	5	2	6	9

 

-       그 다음에는 1번 인덱스와 2 ~ 4번 인덱스 중 최소값과 교체한다.

 

인덱스	0	1	2	3	4
리스트 항목	1	2	5	6	9

 

-       이런 식으로 반복하여 리스트를 정렬한다.

 

 

2>   삽입 정렬 (Insertion Srot) : 해당 값이 어떤 위치에 들어갈지 탐색

 

-       앞에서부터 다음 인덱스 값과 비교하면서 순서를 정렬한다.

 

인덱스	0	1	2	3	4
리스트 항목	5	2	1	6	9

 

-       0번 인덱스와 1번 인덱스를 비교한다. (2가 더 작으므로 0번 인덱스 값으로 교체)

 

인덱스	0	1	2	3	4
리스트 항목	2	5	1	6	9

 

-       2번 인덱스와 1번 인덱스를 비교한다. (1이 더 작으므로 5보다 작으므로 교체하고, 0번 인덱스 값인 2보다도 작으니까 첫 번째로 이동)

 

인덱스	0	1	2	3	4
리스트 항목	1	2	5	6	9

 

-       3번, 4번 인덱스는 앞의 인덱스 값보다 크므로 정렬이 완성된다.

 

 

- 리스트 탐색 알고리즘

 

1>   선형 탐색 알고리즘 : 처음부터 순서대로 해당 값을 탐색한다.

 

2>   이진 탐색 알고리즘 : 기본이 정렬이 되어있는 리스트가 된 상태로 전체 리스트에서 중간 인덱스 값을 지정하여 값을 비교하여 탐색범위를 줄여간다.

 

리스트 길이	이진 탐색 알고리즘	선형 탐색 알고리즘
16	4개	16개
32	5개	32개
64	6개	64개

 

è  리스트가 길어질수록 이진 탐색 알고리즘이 효율적이다.!

(단, 리스트가 크기 순으로 정렬이 되어있어야 함.)

 

 

* 알고리즘 비교 방식

 

1>   시간 복잡도 (Time Complexity)

 

è  같은 크기의 데이터를 처리하는데 상대적으로 오래 걸리는 알고리즘을 시간 복잡도가 크다고 한다.

 

2>   Big-O 점근 표기법 (n이 크다는 가정하에 다른 숫자는 무시하고 표기)