โปรแกรม C++ อัลกอริทึม Selection Sort

Selection Sort

ในเทคนิคการจัดเรียงแบบ Selection Sort รายการจะถูกแบ่งออกเป็น 2 ส่วน ในส่วนหนึ่งทุกองค์ประกอบถูกจัดเรียงแล้ว และอีกส่วนไอเท็มยังไม่ได้จัดเรียง ตรงแรกเราหาข้อมูลสูงสุดหรือต่ำสุดจากอาร์เรย์ หลังจากได้ข้อมูล (สมมติว่าต่ำสุด) เราวางมันที่จุดเริ่มต้นของรายการโดยแทนที่ข้อมูลตำแหน่งแรกด้วยข้อมูลต่ำสุด หลังจากดำเนินการ อาร์เรย์จะเล็กลง ดังนั้นเทคนิคการจัดเรียงนี้จึงเสร็จสิ้น

ความซับซ้อนของ Selection Sort

• Time Complexity: O(n²)

• Space Complexity: O(1)

Input - รายการที่ไม่ได้จัดเรียง: 5 9 7 23 78 20
Output - Array after Sorting: 5 7 9 20 23 78

อัลกอริทึม

selectionSort(array, size)

Input: อาร์เรย์ข้อมูล, และจำนวนรวมในอาร์เรย์

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  for i := 0 ถึง size-2 // หาค่าต่ำสุดจากตำแหน่ง i ถึง size
    iMin := i
    for j := i+1 ถึง size-1
      if array[j] < array[iMin] then
        iMin := j
    สลับ array[i] กับ array[iMin]
สิ้นสุด

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void selectionSort(int *array, int size) {
    int i, j, imin;
    for(i = 0; i < size-1; i++) {
        imin = i;
        for(j = i+1; j < size; j++)
            if(array[j] < array[imin])
                imin = j;
        swap(array[i], array[imin]);
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    selectionSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

ผลลัพธ์ตัวอย่าง

Enter the number of elements: 6
Enter elements: 5 9 7 23 78 20
Array before Sorting: 5 9 7 23 78 20
Array after Sorting: 5 7 9 20 23 78