Программирование на C и C++

Онлайн справочник программиста на C и C++

binary_sort

Аватар пользователя merkul40
вс, 12/24/2017 - 23:17 -- merkul40

двоичный поиск в массиве отличается от линейного тем, что массив до поиска должен быть отсортирован. После сортировки массив дробится пополам, средний элемент сравнивается с искомым значением. Если совпало, значит все, если нет - ищем в каком из двух подмассивов находится искомое значение. Переходим в нужный подмассив, который опять дробится и операция продолжается до совпадения искомого значения со средним элементом.

#include<stdio.h>  
#include<stdlib.h>
#define         SIZE    1000

int binarySearch(int[], int, int, int, int);
//void printRow(int[], int, int, int, int);
int determination(void);
int printing(int num, int Mass[]);
void shakerSort(void);

using namespace std;

int Array[SIZE] = {0};

int main()
{
       
        int key, result;
        determination();
        printing(SIZE, Array);
        shakerSort();
        printf("\n\n\n");
        printing(SIZE, Array);
        printf("Введите искомое число\t");
        scanf("%d", &key);
       
       
        result =  binarySearch(Array, key, 0, (SIZE - 1), SIZE);
       
        //printf("res = %d", result);
       
        if (result != -1)
        {
                printf("Искомое число находится на %d позиции\n\n\n", result);
                }
        else
        {
                printf("Результат отсутствует\n\n\n");
                }
       
        return 0;
        }

int determination()//функция присвоения значений массиву
{
        for (int i = 0; i < SIZE; i++)
        {
                Array [i] = rand() % (SIZE * 3);
                }
       
        }
       
       
int printing(int num, int Mass[])//вывод на экран одномерного массива
{
        for (int i = 0; i < num; i++)
        {
                        printf("%d\t%d\n", i , Mass[i]);
                       
                }
        }

int binarySearch(int A[], int key, int low, int high, int size)
{
        int middle;
       
        while (low <= high)
        {
                middle = (low + high) / 2;
               
                if (key == A [middle])
                {
                        return middle;
                        }
                else if (key < A[middle])
                {
                        high = middle - 1;
                        }
               
                        else
                        {
                                low = middle + 1;
                                }
                }
       
        return -1;
        }
       
void shakerSort() //сортировку массива  производим известным способом

{
        int tmp = 0, high = 0, low = (SIZE - 1);
        while (high < low)
        {
                for (int i = high; i < low; i++)//двигаемся сверху вниз
                {
                        if (Array[i] > Array[i + 1])    //если текущее значение больше
                        {
                                tmp = Array[i];         //следующего меняем их местами
                                Array[i] = Array[i + 1];        //(двигаем его вниз)
                                Array[i + 1] = tmp;                     //
                               
                                }
                                }
                        low--;//обратите внимание, что нижняя граница поднимается
                                        //вверх   
                for (int j = low; j > high; j--)//двигаемся снизу вверх
                {
                        if (Array[j] < Array[j - 1])    //если текущее значение меньше
                        {
                               
                                tmp = Array[j];         //следующего меняем их местами
                                Array[j] = Array[j - 1];        //(двигаем его вверх)
                                Array[j - 1] = tmp;                     //
                               
                                }
                                }
                high++;
                }
       
        }

Я забил в значение SIZE 1000 000. На процессоре q6600 алгоритм выполняется уже минут 20. При этом одно ядро постоянно загружено на 100%.
Если в массиве 10 000 элементов, то алгоритм выполняется за несколько секунд.