Sorting Algorithm 편집하기

'''Sorting Algorithm''' is an algorithm that arranges elements of a list or array in a specific order, typically numerical or lexicographical. Sorting is a fundamental operation in computer science, used in data processing, searching, and optimization.
==Classification of Sorting Algorithms==
Sorting algorithms can be classified based on various criteria:
===By Complexity===
{| class="wikitable"
!Complexity!!Example Algorithms!!Description
|-
|O(n log n)||Merge Sort, Quick Sort, Heap Sort||Efficient sorting algorithms commonly used in practice.
|-
|O(n²)||Bubble Sort, Insertion Sort, Selection Sort||Simple but inefficient for large datasets.
|-
|O(n)||Counting Sort, Radix Sort, Bucket Sort||Used for special cases where elements have constraints.
|}
===By Methodology===
*'''Comparison-Based Sorting:''' Compares elements to determine their order.
**Examples: Merge Sort, Quick Sort, Heap Sort.
*'''Non-Comparison Sorting:''' Uses properties of elements rather than comparisons.
**Examples: Counting Sort, Radix Sort, Bucket Sort.
===By Stability===
*'''Stable Sorting:''' Preserves the relative order of equal elements.
**Examples: Merge Sort, Bubble Sort, Insertion Sort.
*'''Unstable Sorting:''' Does not guarantee the order of equal elements.
**Examples: Quick Sort, Heap Sort, Selection Sort.
==Common Sorting Algorithms==
===Bubble Sort===
*'''Process:''' Repeatedly swaps adjacent elements if they are in the wrong order.
*'''Time Complexity:''' O(n²).
*'''Best Case:''' O(n) (already sorted list).
*'''Worst Case:''' O(n²) (reversed list).
*'''Stable:''' Yes.
===Selection Sort===
*'''Process:''' Selects the smallest element and swaps it with the first unsorted element.
*'''Time Complexity:''' O(n²).
*'''Stable:''' No.
===Insertion Sort===
*'''Process:''' Inserts each element into its correct position in the sorted section.
*'''Time Complexity:''' O(n²) (worst case), O(n) (best case).
*'''Stable:''' Yes.
===Merge Sort===
*'''Process:''' Recursively divides the array into halves, sorts them, and merges them.
*'''Time Complexity:''' O(n log n).
*'''Stable:''' Yes.
*'''Use Case:''' Efficient for large datasets.
===Quick Sort===
*'''Process:''' Selects a pivot, partitions the array, and recursively sorts the partitions.
*'''Time Complexity:''' O(n log n) (average case), O(n²) (worst case).
*'''Stable:''' No.
*'''Use Case:''' Commonly used in practice due to average-case efficiency.
===Heap Sort===
*'''Process:''' Converts the array into a heap, then extracts the smallest/largest elements.
*'''Time Complexity:''' O(n log n).
*'''Stable:''' No.
===Counting Sort===
*'''Process:''' Counts the occurrences of elements and places them in order.
*'''Time Complexity:''' O(n).
*'''Stable:''' Yes.
*'''Use Case:''' Works only for integer values within a known range.
===Radix Sort===
*'''Process:''' Sorts numbers by processing digits from least significant to most significant.
*'''Time Complexity:''' O(nk), where k is the number of digits.
*'''Stable:''' Yes.
==Comparison of Sorting Algorithms==
{| class="wikitable"
!Algorithm!!Best Case!!Worst Case!!Average Case!!Stable!!In-Place
|-
|Bubble Sort||O(n)||O(n²)||O(n²)||Yes||Yes
|-
|Selection Sort||O(n²)||O(n²)||O(n²)||No||Yes
|-
|Insertion Sort||O(n)||O(n²)||O(n²)||Yes||Yes
|-
|Merge Sort||O(n log n)||O(n log n)||O(n log n)||Yes||No
|-
|Quick Sort||O(n log n)||O(n²)||O(n log n)||No||Yes
|-
|Heap Sort||O(n log n)||O(n log n)||O(n log n)||No||Yes
|-
|Counting Sort||O(n)||O(n + k)||O(n + k)||Yes||No
|-
|Radix Sort||O(nk)||O(nk)||O(nk)||Yes||No
|}
==Applications==
Sorting is widely used in:
*'''Searching Algorithms:''' Binary search requires sorted data.
*'''Databases:''' Query optimization and indexing.
*'''Computer Graphics:''' Sorting polygons for rendering.
*'''Data Science:''' Preprocessing data for analysis and visualization.
==See Also==
*[[Merge Sort]]
*[[Quick Sort]]
*[[Heap Sort]]
*[[Time Complexity]]
*[[Divide-and-Conquer Algorithm]]
*[[Computational Complexity]]
*[[Binary Search]]
[[Category:Algorithm]]