Sorting Algorithm

IT 위키

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[편집 | 원본 편집]

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[편집 | 원본 편집]

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[편집 | 원본 편집]