การเรียงอาเรย์สตริงด้วย Selection Sort ใน C++

โจทย์

Selection Sort algorithm เรียงอาเรย์โดยการหาองค์ประกอบต่ำสุดจากส่วนที่ยังไม่เรียงซ้ำๆ และวางไว้ที่ต้นทาง ในแต่ละรอบของ selection sort องค์ประกอบต่ำสุดจาก unsorted subarray จะถูกเลือกและย้ายไปยัง sorted subarray

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

#include <iostream>
#include <string.h>
using namespace std;
#define MAX_LEN 50
void selectionSort(char arr[][50], int n){
  int i, j, mIndex;
  // ย้ายขอบเขตของ unsorted subarray ทีละอัน
  char minStr[50];
  for (i = 0; i < n-1; i++){
    // หาองค์ประกอบต่ำสุดใน unsorted array
    int mIndex = i;
    strcpy(minStr, arr[i]);
    for (j = i + 1; j < n; j++){
      // ตรวจสอบว่า min มากกว่า arr[j] หรือไม่
      if (strcmp(minStr, arr[j]) > 0){
        // ทำให้ arr[j] เป็น minStr และอัปเดต min_idx
        strcpy(minStr, arr[j]);
        mIndex = j;
      }
    }
    // สลับค่าต่ำสุดกับองค์ประกอบแรก
    if (mIndex != i){
      char temp[50];
      strcpy(temp, arr[i]); //swap item[pos] and item[i]
      strcpy(arr[i], arr[mIndex]);
      strcpy(arr[mIndex], temp);
    }
  }
}
int main(){
  char arr[][50] = {"Tom", "Boyaka", "Matt" ,"Luke"};
  int n = sizeof(arr)/sizeof(arr[0]);
  int i;
  cout<<"Given String is:: Tom, Boyaka, Matt, Luke\n";
  selectionSort(arr, n);
  cout << "\nSelection Sorted is::\n";
  for (i = 0; i < n; i++)
    cout << i << ": " << arr[i] << endl;
  return 0;
}

โปรแกรม C++ ด้านบนเริ่มต้นเลือกองค์ประกอบน้อยที่สุดในอาเรย์และสลับกับองค์ประกอบแรกในอาเรย์ ต่อมา สลับองค์ประกอบที่สองน้อยที่สุดกับองค์ประกอบที่สอง เป็นต้น ดังนั้นสำหรับแต่ละรอบ องค์ประกอบน้อยที่สุดในอาเรย์จะถูกเลือกและวางในตำแหน่งที่ถูกต้องจนกว่าอาเรย์ทั้งหมดจะถูกเรียง ตัวอย่างเช่น selection sort method เรียงสตริงที่กำหนดในลำดับอักขระอักษร ดังนี้

ผลลัพธ์

Given string is:: Tom, Boyaka, Matt, Luke
Selection Sorted:: Boyaka Luke Matt Tom