Kulesh

quick sort and binary search

Dec 20th, 2016
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. void swap (int &a, int &b) {
  6. int c = 0;
  7. c = a;
  8. a = b;
  9. b = c;
  10. }
  11. void qs (int *arr, int low, int high){
  12. int a = high;
  13. int i = low - 1;
  14. if (low < high) {
  15. for (int j = low; j < high; j++){
  16. if (arr[a] > arr[j]) {
  17. i++;
  18. swap (arr[i], arr[j]);
  19. }
  20. }
  21. swap(arr[a], arr[i+1]);
  22. qs (*&arr, low, i);
  23. qs (*&arr, i+2, high);
  24. }
  25. }
  26. void bs (int arr[], int k, int low, int high){
  27. int x = high/2;
  28. if (low < high){
  29. if (arr[x] < k){
  30. bs(arr, k, x+1, high);
  31. } else if (arr[x] > k) {
  32. bs(arr, k, low, x-1);
  33. } else if (arr[x] == k) {
  34. cout << " Found " << k << " at " << x+1;
  35. }
  36. } else if (low == high) {
  37. if (arr[high] == k){
  38. cout << " Found " << k << " at " << high+1;
  39. } else {
  40. cout << "Not Found";
  41. }
  42. }
  43. }
  44. int main() {
  45. int n, s;
  46. cout << "How many integers you want to input : ";
  47. cin >> n;
  48. int array[n];
  49. for (int x = 0; x < n; x++){
  50. cin >> array[x];
  51. }
  52. qs(array, 0, n-1);
  53. cout << "Ouput of sorted array : ";
  54. for (int x = 0; x < n; x++){
  55. cout << array[x] << " ";
  56. }
  57. cout << endl << "Which element do you want to search for? ";
  58. cin >> s;
  59. bs (array, s, 0, n-1);
  60. return 0;
  61. }
RAW Paste Data