จัดเรียงจำนวนบวกและลบด้วยพื้นที่เพิ่มเติมคงที่ใน C++

ภาพรวม

ได้รับอาร์เรย์จำนวนเต็ม arr[] มีทั้งบวกและลบ งานคือจัดเรียงอาร์เรย์ใหม่ให้อิลิเมนต์ทั้งหมดเรียงลำดับ (Sorted) โดยใช้พื้นที่เพิ่มเติมคงที่ (Constant Extra Space) และเทคนิคการเรียกซ้ำ

ตัวอย่าง

อินพุต − int arr[] = {4, 2, -1, -1, 6, -3, 0}

เอาต์พุต − Rearrangement of positive and negative numbers with constant extra space is: -3 -1 -1 0 6 2 4

คำอธิบาย − อาร์เรย์ขนาด 7 มีทั้งบวกและลบ จัดเรียงใหม่ในพื้นที่คงที่ ได้ -3 -1 -1 0 2 4 6

อินพุต − int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}

เอาต์พุต − Rearrangement of positive and negative numbers with constant extra space is: -9 -10 2 3 10 5 8 4

คำอธิบาย − อาร์เรย์ขนาด 8 จัดเรียงในพื้นที่คงที่ ได้ -9 -10 2 3 10 5 8 4

แนวทางการแก้ปัญหา

• รับอาร์เรย์ คำนวณขนาด
• พิมพ์อาร์เรย์ก่อนจัดเรียง
• เรียก Rearrangement(arr, size)
• ภายในฟังก์ชัน:
  • i = 0, j = size - 1
  • while(true):
    • while arr[i] < 0 && i < size i++
    • while arr[j] > 0 && j >= 0 j--
    • หาก i < j สลับ arr[i] กับ arr[j]
    • มิฉะนั้น break
• พิมพ์ผลลัพธ์

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

#include <iostream> 
using namespace std; 

void Rearrangement(int arr[], int size){ 
    int i = 0; 
    int j = size - 1; 
    while(true){ 
        while(arr[i] < 0 && i < size){ 
            i++; 
        } 
        while(arr[j] > 0 && j >= 0){ 
            j--; 
        } 
        if (i < j){ 
            int temp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = temp; 
        } else { 
            break; 
        } 
    } 
} 

int main(){ 
    int arr[] = {4, 2, -1, -1, 6, -3, 0}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    Rearrangement(arr, size); 
    cout << "Rearrangement of positive and negative numbers with constant extra space is: "; 
    for(int i = 0; i < size; i++){ 
        cout << arr[i] << " "; 
    } 
    return 0; 
}

ผลลัพธ์

Rearrangement of positive and negative numbers with constant extra space is: -3 -1 -1 0 6 2 4