Сортировка вставками

@jon_illien · Регистрация: 14.08.2012

Author24 — интернет-сервис помощи студентам

Где-то ошибка в цикле... помогите)

C++

...
 
int array[3] = {3, 2, 1}, min = 0,  a = 0,  b = 0;
 
...
 
for(a = 1; a < size; ++a);
{
    
    for(b = 0; b < a; ++b);
    {
        if(array[a] < array[b])
        {
            min = array[b];
            array[b] = array[a];
            array[a] = min;
        }
    }
}
 
...

Jupiter · 27.08.2012, 00:25

Алгоритмы сортировок

@jon_illien · 27.08.2012, 00:33 **[ТС]**

Сообщение от Jupiter

Алгоритмы сортировок

нееееее.

ValeryS · 27.08.2012, 01:08

Сообщение от jon_illien

нееееее.

очень содержательно

ошибка то в чем выражается??

@jon_illien · 27.08.2012, 01:23 **[ТС]**

Сообщение от ValeryS

очень содержательно

ошибка то в чем выражается??

да, выражалась..., чуть-чуть подредактировал. спасибо

C++

for (a = 1; a < size; ++a) 
    min = array[a]; 
    for (b = a - 1; b >= 0 && array[b] > min; --b)
    {
        array[b + 1] = array[b];
        array[b ] = min;
    }
}

@ovli · 05.09.2012, 12:49

Доброго времени суток, не могу понять как работает код сортировки вставками, пришлось зубрить, а я этого органически не перевариваю, кто нибудь может помочь...

C++

void insertSort(T a[],int size)
{
T x;
int i,j;
for(i=0;i<size;i++)
{
    x=a[i];
    for(j=i-1;j>=0&&a[j]>x;j--)
        a[j+1]=a[j];
    a[j+1]=x;
}
}

1. входим в первый цикл и присваиваем переменной х значение элемента стоящего под № 0 ноль
2. Смотрим на второй цикл и сразу возникает вопрос: почему он без фигурных скобок?
3. Проверяем условие цикла 2, и видим при i=0 j=i-1 j=-1...условие цикла 2 не выполнено и не выполняется никаких действий.
4. Происходит возврат к циклу 1 и становится равным i=1
5. x присваивается x=a[1]
6. смотрим цикл N 2 j=1-1, соответственно j=0, тогда выполняется часть условия j>=0&&a[j]>x, и допустим, что a[j]>x, т.е впереди стоящий элемент больше следующего, будем считать условие выполнено
7.a[j+1]=a[j] элементу a[j+1] присваивается значение a[j] и что по сути равносильно a[i]=a[j] ведь i на одну единицу больше j, а затем a[j+1]=x присваевается значение х, и тут получается абракадабра, или все возвращается назад, a[j+1] присваевается значение предидущее значение a[j+1]...Потом j уменьшается на 1
Короче не фига не понял

@David Sylva · 05.09.2012, 14:41

ovli у тебя ошибка в первом цикле. i должна равняться 1.
вот пример работающего кода

Сортировка вставками

C++

#include <iostream> 
using namespace std; 
 
void InterSort(int* array, int size)  
{  
    int temp; 
    int i, j; 
 
    for ( i = 1; i < size; i++)  
    { 
         temp = array[i]; 
         for ( j = i - 1; j >= 0 && array[j] > temp; --j) 
             array[j+1] = array[j];
             array[j+1] = temp; 
    } 
}
 
 
int main() 
{   
    setlocale(0, "rus");
    const int size = 10;
    int array[size] = { 12, 56, 7, 8, 11, 23, 45, 89, 54, 33 };  
    unsigned int i;
 
    cout << "Исходный массив " << endl;
    for ( i = 0; i < size; i++) 
        cout << array[i] << " "; 
    cout << endl << endl;  
 
    InterSort(array, size);
    cout << "Отсортированный массив " << endl; 
 
    for ( i = 0; i < size; i++) 
        cout << array[i] << " "; 
    cout << endl; 
}

теперь по самой сортировки

C++

int temp; 
    int i, j; 
 
    for ( i = 1; i < size; i++)  
    { 
         temp = array[i]; 
         for ( j = i - 1; j >= 0 && array[j] > temp; --j) 
             array[j+1] = array[j];
             array[j+1] = temp; 
    }

1. Элементу temp присваивается второй элемент в массиве
2. j на один меньше чем i в данном случае первый элемент
3 если j ,больше или равно 0 и первый элемент больше впереди стоящего они меняются местами

В общем сортировка начинается со второго элемента и элементы упорядочиваются с левой стороны от данной итерации цикла.

@ovli · 05.09.2012, 15:05

Спасибо, но ошибка не у меня, а в учебном материале "Шага"

Jupiter Каратель 6609 / 4028 / 401 Регистрация: 26.03.2010 Сообщений: 9,273 Записей в блоге: 1
	27.08.2012, 00:25	2
	Алгоритмы сортировок 1

@jon_illien 3 / 3 / 1 Регистрация: 14.08.2012 Сообщений: 78
	27.08.2012, 00:33 [ТС]	3
	Сообщение от Jupiter Алгоритмы сортировок нееееее. 0

ValeryS Модератор 8909 / 6678 / 918 Регистрация: 14.02.2011 Сообщений: 23,524
	27.08.2012, 01:08	4
	Сообщение от jon_illien нееееее. очень содержательно ошибка то в чем выражается?? 1

@ovli 0 / 0 / 0 Регистрация: 04.08.2012 Сообщений: 16
	05.09.2012, 15:05	8
	Спасибо, но ошибка не у меня, а в учебном материале "Шага" Миниатюры 0