ปัญหาน็อตและโบลท์

รายชื่อน็อตต่างๆ และรายการสลักเกลียวอื่นๆ งานของเราคือค้นหาน็อตและโบลท์ที่ตรงกันจากรายการที่กำหนด และกำหนดน็อตนั้นกับโบลท์ เมื่อจับคู่แล้ว

ปัญหานี้แก้ไขได้ด้วยเทคนิคการเรียงลำดับอย่างรวดเร็ว โดยการนำองค์ประกอบสุดท้ายของสลักเกลียวมาเป็นเดือย ให้จัดเรียงรายการน็อตใหม่และรับตำแหน่งสุดท้ายของน็อตที่มีโบลต์เป็นองค์ประกอบเดือย หลังจากแบ่งพาร์ติชั่นรายการน็อตแล้ว เราสามารถแบ่งพาร์ติชั่นรายการน็อตโดยใช้น็อตที่เลือก งานเดียวกันจะดำเนินการสำหรับรายการย่อยด้านซ้ายและขวาเพื่อรับการแข่งขันทั้งหมด

อินพุตและเอาต์พุต

Input:
The lists of locks and keys.
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Output:
After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

อัลกอริทึม

พาร์ติชั่น(อาร์เรย์ ต่ำ สูง เดือย)

ป้อนข้อมูล: หนึ่งอาร์เรย์ ดัชนีต่ำและสูง องค์ประกอบเดือย

ผลลัพธ์: ตำแหน่งสุดท้ายขององค์ประกอบเดือย

Begin
   i := low
   for j in range low to high, do
      if array[j] < pivot, then
         swap array[i] and array[j]
         increase i by 1
      else if array[j] = pivot, then
         swap array[j] and array[high]
         decrease j by 1
   done

   swap array[i] and array[high]
   return i
End

nutAndBoltMatch(น็อต โบลท์ ต่ำ สูง)

ป้อนข้อมูล: รายการน็อต รายการสลักเกลียว ดัชนีล่างและสูงกว่าของอาร์เรย์

ผลลัพธ์: แสดงว่าน็อตตัวไหนใช้น็อตตัวไหน

Begin
   pivotLoc := partition(nuts, low, high, bolts[high])
   partition(bolts, low, high, nuts[pivotLoc])
   nutAndBoltMatch(nuts, bolts, low, pivotLoc-1)
   nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high)
End

ตัวอย่าง

#include<iostream>
using namespace std;

void show(char array[], int n) {
   for(int i = 0; i<n; i++)
      cout << array[i] << " ";
}

int partition(char array[], int low, int high, char pivot) {    //find location of pivot for quick sort
   int i = low;
   for(int j = low; j<high; j++) {
      if(array[j] <pivot) {    //when jth element less than pivot, swap ith and jth element
         swap(array[i], array[j]);
         i++;
      }else if(array[j] == pivot) {    //when jth element is same as pivot, swap jth and last element
         swap(array[j], array[high]);
         j--;
      }
   }
   swap(array[i], array[high]);
   return i;    //the location of pivot element
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
   if(low < high) {
      int pivotLoc = partition(nuts, low, high, bolts[high]);   //choose item from bolt to nut partitioning
      partition(bolts, low, high, nuts[pivotLoc]);    //place previous pivot location in bolt also
      nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1);
      nutAndBoltMatch(nuts, bolts, pivotLoc+1, high);
   }
}

int main() {
   char nuts[] = {')','@','*','^','(','%','!','$','&','#'};
   char bolts[] = {'!','(','#','%',')','^','&','*','$','@'};
   int n = 10;
   nutAndBoltMatch(nuts, bolts, 0, n-1);
   cout << "After matching nuts and bolts:"<< endl;
   cout << "Nuts:  "; show(nuts, n); cout << endl;
   cout << "Bolts: "; show(bolts, n); cout << endl;
}

ผลลัพธ์

After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^