Mảng được sắp xếp trong C ++

Ở đây chúng ta sẽ thấy một số khái niệm cơ bản về mảng đã sắp xếp. Các mảng là cấu trúc dữ liệu đồng nhất để chứa cùng một loại dữ liệu trong một số vị trí bộ nhớ liên tiếp. Đôi khi chúng ta cần sắp xếp các phần tử để sử dụng chúng. Ngoài ra, chúng ta có thể tạo một mảng được sắp xếp. Điều đó sẽ luôn được sắp xếp.

Trong trường hợp này, chúng ta sẽ thấy các thuật toán chèn và xóa vào mảng đã sắp xếp. Nếu chúng ta chèn một số phần tử vào đó, nó sẽ tự động được đặt ở vị trí đã sắp xếp. Vì vậy, chúng ta không cần phải sắp xếp lại sau khi chèn. Khi chúng ta xóa, nó sẽ xóa phần tử và lấp đầy khoảng trống bằng cách dịch chuyển các phần tử sang phải. Vì chúng tôi đang sử dụng mảng được sắp xếp, chúng tôi sẽ sử dụng thuật toán tìm kiếm nhị phân để tìm phần tử trước khi xóa nó.

Thuật toán

insertSorted(arr, n, key):
Begin
   if n >= max size of the array, then return
   otherwise i := n – 1
   while i >= 0 and arr[i] > key, do
      arr[i + 1] := arr[i]
      i := i - 1
   done
   arr[i + 1] := key
   n := n + 1
End
deleteSorted(arr, n, key):
Begin
   pos := search key into arr
   if pos is -1, then item is not found, and return
   otherwise i := pos
   while i < n – 1, do
      arr[i] := arr[i + 1]
      i := i + 1
   done
   n := n + 1
End

Ví dụ

#include <iostream>
#define MAX 10
using namespace std;
void display(int arr[], int n){
   for(int i = 0; i <n; i++){
      cout << arr[i] << " ";
   }
   cout << endl;
}
int search(int arr[], int low, int high, int key){
   if (high < low)
      return -1;
   int mid = (low + high) / 2; /*low + (high - low)/2;*/
   if (key == arr[mid])
      return mid;
   if (key > arr[mid])
      return search(arr, (mid + 1), high, key);
   return search(arr, low, (mid - 1), key);
}
void insertSorted(int arr[], int &n, int key){
   if (n >= MAX){
      cout << "No place to insert";
      return;
   }
   int i;
   for (i = n - 1; (i >= 0 && arr[i] > key); i--)
      arr[i + 1] = arr[i];
   arr[i + 1] = key;
   n = n + 1;
}
void deleteSorted(int arr[], int &n, int key){
   int key_pos = search(arr, 0, n, key);
   if(key_pos == -1){
      cout << "Element is not present." << endl;
      return;
   }
   int i;
   for (i = key_pos; i < n - 1; i++)
      arr[i] = arr[i + 1];
   n = n - 1;
}
int main() {
   int arr[MAX];
   int n = 0;
   insertSorted(arr, n, 10);
   insertSorted(arr, n, 20);
   insertSorted(arr, n, 30);
   insertSorted(arr, n, 40);
   insertSorted(arr, n, 50);
   insertSorted(arr, n, 60);
   insertSorted(arr, n, 70);
   display(arr, n);
   deleteSorted(arr, n, 35);
   deleteSorted(arr, n, 40);
   deleteSorted(arr, n, 60);
   display(arr, n);
}

Đầu ra

10 20 30 40 50 60 70
Element is not present.
10 20 30 50 70