Быстрая сортировка

@MariaK · Регистрация: 10.03.2013

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

Помогите! Не могу найти ошибку. Написать программу с помощью метода быстрой сортировки. Выбирать в качестве m – среднее арифметическое всех элементов массива. Оценить глубину рекурсии, количество сравнений ключа и количество перестановок.

VB.NET
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Imports System.Math
Public Class Form1
    Dim n As Integer = 10
    Dim A(0 To n - 1) As Integer
    Dim Glubina As Integer
    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim min, max As Integer
        min = 0
        max = n - 1
        Randomize()
        For i = 0 To n - 1
            A(i) = Rnd() * 100
            Console.Write(A(i) & " ")
        Next
        Console.WriteLine()
        QuickSort(A, min, max)
        Console.WriteLine("Глубина рекурсии:" & Glubina)
    End Sub
    Public Sub QuickSort(ByRef A() As Integer, ByVal min As Integer, ByVal max As Integer)
        Dim m, L, H, w, sum As Integer
        L = min
        H = max
        For i = 0 To H
            sum = sum + A(i)
        Next i
        m = Round(sum / (H - L))
        Console.WriteLine("Среднее " & m)
        Do Until (L > H)
            Do While A(L) < m
                L = L + 1
            Loop
            Do While A(H) > m
                H = H - 1
            Loop
            If L <= H Then
                w = A(L)
                A(L) = A(H)
                A(H) = w
                L = L + 1
                H = H - 1
                For i = 1 To n
                    Console.Write(A(i) & " ")
                Next
                Console.WriteLine()
            End If
        Loop
        If min < H Then QuickSort(A, min, H) : Glubina = Glubina + 1
        If max > L Then QuickSort(A, L, max) : Glubina = Glubina + 1
    End Sub
End Class

@Catstail · 15.05.2013, 16:34

Строка 27 должна иметь вид:

VB.NET
1
m = Round(sum / (H - L+1))

@MariaK · 15.05.2013, 16:55 **[ТС]**

Суть в том, что мне кажется я неправильное значение m передаю. Потому что при отладке выдает ошибку в консоль.

VB.NET
1
2
3
4
5
 For i = 1 To n
                    Console.Write(A(i) & " ")
                Next
                Console.WriteLine()
            End If

@Catstail · 15.05.2013, 16:59

Вот твой код, переложенный на VB (здесь, вообще-то, раздел VB, а не VB.Net). Код работает:

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Dim Glubina As Integer
Sub Test()
Dim X(1 To 40) As Integer
    Randomize
    For i% = 1 To 40
        X(i%) = 10 * Rnd()
    Next i%
    QuickSort X(), 1, 10
End Sub
 
Public Sub QuickSort(ByRef A() As Integer, ByVal min As Integer, ByVal max As Integer)
Dim m As Integer, L As Integer, H As Integer, w As Integer, sum As Integer
        L = min
        H = max
        For i = L To H
            sum = sum + A(i)
        Next i
        m = Round(sum / (H - L + 1))
        Debug.Print "Среднее " & m
        Do Until (L > H)
            Do While A(L) < m
                L = L + 1
            Loop
            Do While A(H) > m
                H = H - 1
            Loop
            If L <= H Then
                w = A(L)
                A(L) = A(H)
                A(H) = w
                L = L + 1
                H = H - 1
                For i = 1 To 10
                    Debug.Print A(i) & " ";
                Next
                Debug.Print
            End If
        Loop
        If min < H Then
           QuickSort A, min, H
           Glubina = Glubina + 1
        End If
        If max > L Then
           QuickSort A, L, max
           Glubina = Glubina + 1
        End If
End Sub

А пока я не добавил единицу - он циклил.

@MariaK · 15.05.2013, 17:07 **[ТС]**

ой

у меня не работает, он застревает во время отладки и все

@Catstail · 15.05.2013, 17:16

покажи, как ты его запускаешь.

@MariaK · 15.05.2013, 17:49 **[ТС]**

запускаю шаг с заходом, что отследить. и когда доходит до console пишет, что индекс находился вне границ массива

Добавлено через 4 минуты
я нашла ошибку, спасибо)

@Апострофф · 15.05.2013, 18:11

MariaK, расскажите, что за ошибка была, кому-нибудь может пригодиться?

Catstail, в Sub Test() вызов QuickSort правильнее сделать так

Visual Basic
1
QuickSort X(), lbound(x), ubound(x)

А Вы отсортировали только первую четверть массива.

@Pro_grammer · 15.05.2013, 18:21

Если кому интересно, быстрая сортировка "из книжки"
Примеры из книги "Готовые алгоритмы на Visual Basic".

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
' ************************************************
' FQuick.BAS
'
' Source code for quicksort using MemCopy.
' ************************************************
' Copyright (C) 1997 John Wiley & Sons, Inc.
' ************************************************
Option Explicit
 
Global CutOff As Long
 
' ************************************************
' Quicksort with:
'   - Uses Rnd to select a random dividing value
'   - Stops when there are fewer than CutOff items
'       left to sort. It then finishes using
'       SelectionSort.
' ************************************************
Public Sub Quicksort(List() As Long, ByVal min As Long, ByVal max As Long)
Dim med_value As Long
Dim hi As Long
Dim lo As Long
Dim i As Long
 
    ' If the list has no more than CutOff elements,
    ' finish it off with SelectionSort.
    If max - min < CutOff Then
        Selectionsort List(), min, max
        Exit Sub
    End If
 
    ' Pick the dividing value.
    i = Int((max - min + 1) * Rnd + min)
    med_value = List(i)
 
    ' Swap it to the front.
    List(i) = List(min)
 
    lo = min
    hi = max
    Do
        ' Look down from hi for a value < med_value.
        Do While List(hi) >= med_value
            hi = hi - 1
            If hi <= lo Then Exit Do
        Loop
        If hi <= lo Then
            List(lo) = med_value
            Exit Do
        End If
 
        ' Swap the lo and hi values.
        List(lo) = List(hi)
        
        ' Look up from lo for a value >= med_value.
        lo = lo + 1
        Do While List(lo) < med_value
            lo = lo + 1
            If lo >= hi Then Exit Do
        Loop
        If lo >= hi Then
            lo = hi
            List(hi) = med_value
            Exit Do
        End If
        
        ' Swap the lo and hi values.
        List(hi) = List(lo)
    Loop
    
    ' Sort the two sublists.
    Quicksort List(), min, lo - 1
    Quicksort List(), lo + 1, max
End Sub

@Апострофф · 15.05.2013, 18:26

Pro_grammer, Selectionsort List(), min, max приложите пожалуйста

@Pro_grammer · 15.05.2013, 18:36

Сообщение от Апострофф

приложите

Я уж тогда лучше весь проект. Вернее там в одном архиве несколько проектов. Несколько видов сортировки + анализ их по времени + при различных исходных данных.
Обратная задача - рассортировка. Поиск наибольшего и т.п. полезные алгоритмы.

@Апострофф · 15.05.2013, 18:42

весь проект - это хорошо!
А я хотел собрать один законченный пример в одном Вашем сообщении - Быстрая сортировка (А там упоминается Selectionsort).

@Catstail · 15.05.2013, 19:57

Сообщение от Апострофф

А Вы отсортировали только первую четверть массива.

- да... Торопился, как обычно.

Добавлено через 1 минуту

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

Обратная задача - рассортировка.

- обратная задача обычно называется перемешиванием.

Добавлено через 1 минуту

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

Суть в том, что мне кажется я неправильное значение m передаю

- о чем я и говорю.

@MariaK · 15.05.2013, 20:11 **[ТС]**

VB.NET
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Imports System.Math
Public Class Form1
    Dim n As Integer = 10
    Dim A(0 To n - 1) As Integer
    Dim Glubina As Integer
    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim min, max As Integer
        min = 0
        max = n - 1
        Randomize()
        For i = 0 To n - 1
            A(i) = Rnd() * 100
            Console.Write(A(i) & " ")
        Next
        Console.WriteLine()
        QuickSort(A, min, max)
        Console.WriteLine("Глубина рекурсии:" & Glubina)
    End Sub
    Public Sub QuickSort(ByRef A() As Integer, ByVal min As Integer, ByVal max As Integer)
        Dim m, L, H, w, sum As Integer
        L = min
        H = max
        For i = L To H
            sum = sum + A(i)
        Next i
        m = Round(sum / (H - L + 1))
        Console.WriteLine("Среднее " & m)
        Do Until (L > H)
            Do While A(L) < m
                L = L + 1
            Loop
            Do While A(H) > m
                H = H - 1
            Loop
            If L <= H Then
                w = A(L)
                A(L) = A(H)
                A(H) = w
                L = L + 1
                H = H - 1
                For i = 0 To n - 1
                    Console.Write(A(i) & " ")
                Next
                Console.WriteLine()
            End If
        Loop
        If min < H Then QuickSort(A, min, H) : Glubina = Glubina + 1
        If max > L Then QuickSort(A, L, max) : Glubina = Glubina + 1
    End Sub
End Class

@Pro_grammer · 15.05.2013, 20:12

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

обратная задача обычно называется перемешиванием.

Точно! А то я перевожу Unsorting, а мне в голову лезет "все подряд" (с) Google translator

@MariaK · 15.05.2013, 20:13 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

Быстрая сортировка

Решение

Решение

@MariaK 3 / 3 / 2 Регистрация: 10.03.2013 Сообщений: 80
	15.05.2013, 17:07 [ТС]
	ой у меня не работает, он застревает во время отладки и все 0

@Catstail Супер-модератор 38200 / 21132 / 4310 Регистрация: 12.02.2012 Сообщений: 34,738 Записей в блоге: 14
	15.05.2013, 17:16
	покажи, как ты его запускаешь. 0

@MariaK 3 / 3 / 2 Регистрация: 10.03.2013 Сообщений: 80
	15.05.2013, 17:49 [ТС]
	запускаю шаг с заходом, что отследить. и когда доходит до console пишет, что индекс находился вне границ массива Добавлено через 4 минуты я нашла ошибку, спасибо) 0

@Апострофф 9908 / 3928 / 742 Регистрация: 11.10.2011 Сообщений: 5,908
	15.05.2013, 18:26
	Pro_grammer, Selectionsort List(), min, max приложите пожалуйста 0

@Апострофф 9908 / 3928 / 742 Регистрация: 11.10.2011 Сообщений: 5,908
	15.05.2013, 18:42
	весь проект - это хорошо! А я хотел собрать один законченный пример в одном Вашем сообщении - Быстрая сортировка (А там упоминается Selectionsort). 0

@MariaK 3 / 3 / 2 Регистрация: 10.03.2013 Сообщений: 80
	15.05.2013, 20:13 [ТС]
	не пойму... это когда случайный элемент выбирается? 0