JavaRush /Курсы /Harvard CS50 /Алгоритмы сортировки. Сортировка выбором

Алгоритмы сортировки. Сортировка выбором

Harvard CS50

3 уровень , 8 лекция

Открыта

Внимание! Практически весь материал этой лекции был в видеолекции.

Если вы всё хорошо усвоили, просто пробегитесь глазами и переходите дальше.

Есть массив чисел. Нужно его отсортировать. Для простоты будем считать, что мы сортируем целые числа в порядке возрастания (от меньшего к большему). Существует несколько известных способов провернуть этот процесс. Плюс, вы всегда можете пофантазировать на тему и придумать модификацию алгоритма.

Сортировка выбором

Основная идея — разбить наш список на две части, отсортированную и неотсортированную. На каждом шаге алгоритма новое число перемещается из неотсортированной части в отсортированную, и так пока все числа не окажутся в отсортированной части.

Находим минимальное неотсортированное значение.
Меняем местами это значение с первым неотсортированным значением, ставя его таким образом в конец отсортированного массива.
Если остались неотсортированные значения, возвращаемся к шагу 1.

На первом шаге все значения являются неотсортированными. Назовем неотсортированную часть — Unsorted, а отсортированную — Sorted (это просто английские слова, и делаем мы это только потому, что Sorted — гораздо короче, чем «Отсортированная часть» и будет лучше смотреться на картинках).

Алгоритмы сортировки. Сортировка выбором - 2

Находим минимальное число в неотсортированной части массива (то есть, на этом шаге — во всем массиве). Это число 2. Теперь меняем его с первым среди неотсортированных и ставим его в конец отсортированного массива (на этом шаге — на первое место). На этом шаге это первое число в массиве, то есть 3.

Алгоритмы сортировки. Сортировка выбором - 3

Шаг второй. На число 2 мы не смотрим, оно уже в отсортированном подмассиве. Начинаем искать минимальное, начиная со второго элемента, это 5. Убеждаемся, что 3 — минимальное среди неотсортированных, 5 — первое среди неотсортированных. Меняем их местами и прибавляем 3 к отсортированному подмассиву.

Алгоритмы сортировки. Сортировка выбором - 4

На третьем шаге мы видим, что в неотсортированном подмассиве самое маленькое число — 4. Меняем его с первым числом среди неотсортированных — 5.

Алгоритмы сортировки. Сортировка выбором - 5

На четвертом шаге мы обнаруживаем, что в неотсортированном массиве минимальное число — 5. Меняем его с 6 и прибавляем к отсортированному подмассиву.

Алгоритмы сортировки. Сортировка выбором - 6

Когда среди неотсортированных остается только одно число (наибольшее), это значит, что весь массив отсортирован!

Алгоритмы сортировки. Сортировка выбором - 7

Вот как выглядит реализация массива в коде. Попробуйте сделать его самостоятельно.

Алгоритмы сортировки. Сортировка выбором - 8

В обоих, самом лучшем и самом худшем случаях, чтобы найти минимальный неотсортированный элемент, мы должны сравнить каждый элемент с каждым элементом неотсортированного массива, и делать это мы будем на каждой итерации. Но нам нужно просматривать не весь список, а только неотсортированную часть. Меняет ли это скорость алгоритма? На первом шаге для массива из 5 элементов мы делаем 4 сравнения, на втором — 3, на третьем — 2. Чтобы получить количество сравнений, нам нужно сложить все эти числа. Мы получаем сумму

Алгоритмы сортировки. Сортировка выбором - 9

Таким образом, ожидаемая скорость алгоритма в лучшем и худшем случае — Θ(n²) = O(n²).

Не самый эффективный алгоритм! Тем не менее, для учебных целей и для небольших массивов данных — вполне применимый.

Предыдущая Предыдущая лекция

Следующая Следующая лекция

Комментарии (19)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

JavaRusher853 Уровень 36

6 марта 2024

Простите конечно, вопрос не в тему, но я пришел изучать Java или C++(или что это за язык который люди в комментах пишут)?

FeatHonnar Уровень 16

21 сентября 2022

Ломал голову долго, действительно, в этом курсе надо больше догадываться, чем учить, но вроде вышло даже симпатично и коротко


#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main() {
    string num = get_string("Ваши числа:\n");
    int n = strlen(num), j = 0;
    for (int i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            int min = i;
            if (num[j] < num[i]) {
                min = j;
            }
            if (min != i) {
                int a = num[i];
                num[i] = num[j];
                num[j] = a;
            }
        }
    }
    printf("%s", num);
}

Ярослав Уровень 0

27 августа 2020

В предварительном плане программы 2 ошибки. Скорее всего спецом. Тупо не списывайте, думайте! #include <stdio.h> #include <string.h> int main(void) { char massive[] = "13524"; for (int i=0, lenth=strlen(massive); i < lenth - 1; i++ ) { int j = i + 1; do { if (massive[j] < massive[i]) { char temp = massive[i]; massive[i] = massive[j]; massive[j] = temp; } j++; } while (j < lenth ); } }

Daniel Ches Уровень 0

13 июля 2020


#include <stdio.h>
#include <cs50.h>
#include <string.h>

int main()
{
    string n = get_string("");
    for (int i = 0, min, c; i<strlen(n)-1; i++)
    {
        min=n[i]-'0';
        for (int j =i+1; j<strlen(n); j++)
        {
            if (n[j]-'0'<min)
            {
                min = n[j]-'0';
            }
            if (min !=n[i]-'0')
            {
                c = n[i];
                n[i] = n[j];
                n[j] = c;
            }
        }
    }
    printf("%s\n", n);
}

Daniel Ches Уровень 0

13 июля 2020

Случайно получилось сделать ещё короче).


#include <stdio.h>
#include <string.h>
#include <cs50.h>

int main()
{
    string n = get_string("");
    for (int i = 0, c; i<strlen(n)-1; i++)
        {
            for (int j = i+1; j<strlen(n); j++)
            {
                if (n[i]>n[j])
                {
                    c = n[i];
                    n[i] = n[j];
                    n[j] = c;
                }
            }
        }
    printf("%s", n);
}

Максим Уровень 17

10 июля 2020

В видео ничего полезного, в целом как и во всём этом, так и не понял как использовать sort на практике.

xacker Уровень 5

15 июня 2020

Стандартные библиотеки, обмен значений - XOR.


//Sort Choice
#include <stdio.h>
#include <stdlib.h>

#define MAX_AMOUNT 50

int main(int argc, char* argv[])
{
	if(argc < 2)
	{
		fprintf(stderr, "Not enough arguments\n");
		return 1;
	}
	if(argc > 2)
	{
		fprintf(stderr, "Too many arguments\n");
		return 1;
	}

	int amount = atoi(argv[1]);
	int array[MAX_AMOUNT] = {0};

	for (int i = 0; i < amount; ++i)
	{
		scanf("%d", &array[i]);
	}

	int min = 0;

	for (int i = 0; i < amount - 1 ; ++i)
	{
		min = i;
		for (int j = i + 1; j < amount; ++j)
		{
			if (array[j] < array[min]) min = j;
		}
		if (min != i)
		{
			array[i] = array[i] ^ array [min];
			array[min] = array[i] ^ array [min];
			array[i] = array[i] ^ array [min];
		}
	}

	printf("Sorted array: ");
	
	for (int i = 0; i < amount; ++i)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

Ихтияр Кадыров Уровень 1

15 марта 2020

/* Комментарий удален */

АМ Уровень 2

21 октября 2019

На вход принимаются аргументы командной строки #include <stdio.h> #include <cs50.h> #include <string.h> #include <stdlib.h> #include <ctype.h> int main (int argc, string argv[]){ if(argc < 2){ //запрашиваем не меннее двух аргументов printf("Нужно ввести более 1 аргумента!\n"); return 1; } int m = argc - 1; //в переменную записываем длинну кроме первого элемента int box[m]; //объявляем массив размером m //перебираем все строки, начинаем со 2 элемента,чтобы не учитывать команду for(int i = 1; i <= m; i++){ //перебираем каждый символ каждой строки for(int j = 0, n = strlen(argv[i]); j < n; j++ ){ if(isdigit(argv[i][j]) == false){ //если символ не является цифрой -завершаем printf("Массив должен состоять только из чисел!\n"); return 1; } } box[i] = atoi(argv[i]); //переводим каждую отдельную строку в целочисленный символ } for(int i = 1; i <= m; i++){ int min = box[i]; //выбираем 1 элемент как минимальный и перебираем for(int j = i + 1; j <= m; j++ ){//со 2 элемента для установки нового мин. элемента if(box[j] < min){ //если находим новый мин. элемент меняем местами min = box[j]; box[j] = box[i]; box[i] = min; } } } printf("Отсортировано: "); for(int i = 1; i <= m; i++ ) printf("%i ", box[i]); printf("\n"); }

jane_belousova Уровень 0

31 августа 2018

#include <cs50.h> #include <stdio.h> int main () { int n=get_int("Сколько чисел в массиве?\n"); float a[n]; for(int k=0; k<n; k++) { printf("Введите число %d: ", k+1); scanf("%f", &a[k]); } printf("Числа отсортированы по возрастанию:"); float min; for(int i=0; i<n-1; i++) { min=a[i]; for(int j=i+1;j<n; j++) { if(a[i]>a[j]) { min=a[j]; a[j]=a[i]; a[i]=min; } } } for(int m=0; m<n; m++) { printf("%.2f; ", a[m]); } printf("\n"); }

Андрей Уровень 1

7 августа 2018

Массив чисел вводится с помощью аргументов командной строки:


#include <stdio.h> // printf
#include <cs50.h> // type string
#include <string.h> // strlen
#include <ctype.h>  // isdigit
#include <stdlib.h> // atoi

int main(int argc, string argv[]){
    int i, j, arr[argc-1], indxmin, swap;
    for(i=0;i<argc-1;i++){ // Инициализация массива и проверка на корректность вводимых данных
        for(j=0; j<strlen(argv[i+1]);j++)
            if (isdigit(argv[i+1][j])==0) {
                printf("Вы ввели не числовой массив!");
                return -1; }
        arr[i]=atoi(argv[i+1]);
    }
    for(i=0;i<argc-2;i++){ // Сортируем
        indxmin=i;
        for(j=i+1; j<argc-1;j++) if (arr[j]<arr[indxmin]) indxmin=j;
        if (indxmin!=i) {
           swap=arr[i];
           arr[i]=arr[indxmin];
           arr[indxmin]=swap;
        }
    }
    for(i=0;i<argc-1;i++) printf("%d ", arr[i]);
    printf("\n");
}

jane_belousova Уровень 0

31 августа 2018

Зачем последний if?? Ведь в предыдущем if ты задаешь значение indmin=i+1

Андрей Уровень 1

6 сентября 2018

И...? В строке после indxmin=i стоит цикл, в котором при обнаружении меньшего числа значение индекса indxmin изменяется. Последний if как раз и проверяет, что нашлось число меньше текущего (раз индекс изменился). Если бы вы читали код подробно, а не выборочно, то такого "странного" вопроса бы не возникло.

jane_belousova Уровень 0

6 сентября 2018

Спасибо, за ответ. У вас тут интересный момент, который я в своей проге не учла :( Сначала находите наименьший индекс, возможно он будет меняться несколько раз, а потом один раз меняете значения!! У меня же они меняются каждый раз, когда находится меньший индекс. p.s. Не заметила отсутствие скобочки после for, что к нему относится один if