Бағдарламасы бойынша практикум ( пәннің атауы) Тақырып: С++ тілінде массивтерді сұрыптау және іздеуді ұйымдастыру

Мазмұны

1 Пәндік аймақты сипаттау

1.1 Бағдарламалау тілдерінің жіктелуі

1.2 С++ бағдарламалау тілі

1.2.1 С++ тілінің негізгі операторлары

1.2.2 Массивтер

1.2.3 Көрсеткіштер

1.3 Жобалауға міндеттерді қою

1.4 Әзірленетін қосымшаға қойылатын талаптарды негіздеу

2 Сұрыптау және іздеу алгоритмдеріне шолу

2.1 Қарапайым алмасу әдісі арқылы сұрыптау

2.2 Таңдау әдісі арқылы сұрыптау

2.3 Көпіршік әдісі арқылы сұрыптау

2.4 Шейкер әдісі арқылы сұрыптау

2.5 Екілік әдісі арқылы сұрыптау

2.6 Бинарлы іздеу алгоритмі

2.7 Интерполяциялық іздеу алгоритмі

2.8 Решето Эратостен іздеу алгоритмі

3. Бағдарламалық қамтаманы жүзеге асыру

3.1 Қолданушыға нұсқаулық

3.2 Тестілеу нәтижелері

Қорытынды

Қолданылған әдебитеттер тізімі (2012 ж. жоғары болуы керек)

Қосымша А (код программы)

Кіріспе
Қазіргі ақпараттық технологиялар әлемі өте белсенді дамуда. Оның негізгі құрылыс блоктарының бірі-бағдарламалау.Бағдарламалау тілі-белгілі бір мәселелерді шешу үшін компьютерге немесе есептеу құрылғысына арналған ережелер жиынтығы. "Бағдарламалау тілі" термині әдетте BASIC, C, C++, COBOL, Java, FORTRAN, Ada, Pascal сияқты жоғары деңгейлі тілдерге жатады.

Компьютер тек бірліктер мен нөлдер түріндегі мәндерді түсінеді. Алайда, осы деңгейде бағдарламалау бағдарламашы үшін өте қиын міндет.

Жоғары деңгейлі бағдарламалау тілдері адамға бағытталған, оған жақын және түсінікті тілдер деп аталады. Мұндай тілдерде компьютерлік архитектураның ерекшеліктері ескерілмейді. Осы тілдердің көмегімен бастапқы мәтіндер деңгейінде жасалған бағдарламалар тиісті тілдің аудармашысы бар басқа платформаларға оңай ауысады. Жоғары деңгейлі тілдердің құрылуы үшінші буын бағдарламалау тілдерінің пайда болуымен сәйкес келеді. Бұл әмбебап тілдер, олардың көмегімен кез-келген саладағы мәселелерді шешуге болады.

Жоғары деңгейлі тіл машиналық кодқа қарағанда абстракцияның жоғары деңгейін білдіреді. Регистрлермен, жад адрестерімен және қоңырау стектерімен күресудің орнына, жоғары деңгейлі тілдер айнымалылармен, массивтермен, объектілермен, күрделі арифметикалық немесе логикалық өрнектермен, ішкі бағдарламалармен және функциялармен, ағындармен, блоктармен және басқа да дерексіз компьютерлік ғылым тұжырымдамаларымен айналысады, бағдарламаның оңтайлы тиімділігімен салыстырғанда пайдалану ыңғайлылығына назар аударады.Әдетте, бұл тілдерге бір жолға осындай функцияны сипаттауға мүмкіндік беретін қуатты операторлар кіреді, оны жүзеге асыру үшін жас буын тілдерінде мыңдаған бастапқы код жолдары қажет болады. Бұл ұрпақтың тілдері: C / C++ (C++) және Java. Бұл қазіргі заманғы бағдарламалық жасақтаманы әзірлеудің көптеген салаларында қолданылатын өте танымал бағдарламалау тілдері. Бұл жұмыстың өзектілігі.

Бұл жұмыстың мақсаты С (С++) және Java бағдарламалау тілдерінің пайда болу және даму тарихын зерттеу. Тиісінше, зерттеу объектілері С, С++ және Java сияқты тілдер болып табылады және олардың пайда болу және даму тарихын зерттеу тақырыбы болып табылады.

Бұл жұмыстың өзектілігі өте үлкен, өйткені бұл тілдер барлық жерде қолданылады және ақпараттық технологиялар әлеміне қатты әсер етеді.

Курстық жоба аясында келесі міндеттер шешілуі керек:

1. 
   "бағдарламалау" ұғымын ашу;
   
2. 
   жоғары деңгейлі бағдарламалау тілдерін талдау;
   
3. 
   C, C++ және Java тілдерінің пайда болуы мен дамуын зерттеу;
   
4. 
   осы тілдердің даму келешегін талдау;
   
5. 
   осы саладағы әдебиеттерді зерттеу.
   

1 Пәндік аймақты сипаттау

Қатаң айтқанда, бағдарламалау тілдерін жалпы мақсаттағы және тақырыпқа бағытталған тілдерге бөлу өте шартты, әсіресе кез-келген протокол немесе файл пішімі ресми түрде тіл екенін ескерсек. Белгілі бір міндеттер үшін пәндік-бағдарланған тілдер ретінде қолданылатын жалпы мақсаттағы тілдердің массасы бар, керісінше, Жалпы мақсаттағы тілдер ретінде қолданылатын пәндік-бағдарланған тілдер бар. Сонымен, жалпы мақсаттағы тілдердің бүкіл отбасын құрған ML тілі (Хаскеллді қосқанда) бастапқыда LCF теоремаларын автоматты түрде дәлелдеу жүйесі үшін DSL ретінде жасалды. Жіктеу конвенциясын көрсететін мысал-BNF тілі (және Lex/Yacc компиляторы): бір жағынан, бұл Мета — тілдің жарқын мысалы, екінші жағынан, ол бір нақты тапсырмаға арналған.Тілдік-бағдарлы бағдарламалаудың жетекші зерттеушілері (Мартин Уорд, Пол Хьюдак, Валид Таха және басқалары) пәндік-спецификалық тілдердің классикалық ретінде келесі мысалдарын келтіреді:

Мәтіндік құжаттарды дайындауға арналған TeX / LaTeX;

Perl мәтінді басқаруға арналған;

ДҚБЖ үшін SQL;

Графикалық пайдаланушы интерфейсі үшін Tcl/Tk;

Құжаттарды белгілеу үшін HTML және SGML;

Аппараттық құралдарды сипаттау үшін Verilog және VHDL;

Mathematica және Maple символдық есептеулерге арналған;

Компьютерлік модельдеуге арналған AutoLisp (CAD);

Пролог предикаттарды есептеу тұрғысынан тұжырымдалған тапсырмалар үшін;

Функциялар тұрғысынан тұжырымдалған тапсырмалар үшін ML және Haskell (Хаскелл кейде денотациялық семантика үшін DSL ретінде анықталады).

Валид Тахидің пікірінше, ЯОП позициясынан Microsoft Excel әлемде кеңіненқолданылатын бағдарламалау тілі болып табылады .

Пәнге бағытталған тілдердің басқа мысалдары-дерекқорды басқару тілдері (мұнда SQL-ден басқа, мысалы, FoxPro тілін атауға болады), операциялық жүйелердің командалық тілдері (интерактивті командалық қабықтың тілдері, ең алдымен Unix Shell, JCL тілі сияқты пакеттік тапсырмалар тілдері және Тьюринг бойынша толық емес құрылымдау тілдері).

1.2 С++ бағдарламалау тілі
C++ бағдарламалау тілі әр түрлі қосымшаларды жасауға жарамды статикалық терумен жоғары деңгейлі жалпы мақсаттағы бағдарламалау тілін білдіреді. Бүгінгі таңда С++ - ең танымал және кең таралған тілдердің бірі.

Ол 1969-1973 жылдары Bell Labs компаниясында бағдарламашы Деннис Ритчи (Dennis Ritchie) жасаған Си тіліне негізделген. 1980 жылдардың басында сол кезде Bell Labs компаниясында жұмыс істеген даниялық бағдарламашы Бьерн Страуструп С++ тілін с тіліне кеңейту ретінде жасады. Шын мәнінде, басында c++ тек С тілін объектіге бағытталған бағдарламалаудың кейбір мүмкіндіктерімен толықтырды. Сондықтан Страуструптың өзі оны алдымен "C with classes" ("с сыныптармен") деп атады.

Кейіннен жаңа тіл танымал бола бастады. Оған жаңа мүмкіндіктер қосылды, бұл оны тек si-ге ғана емес, жаңа бағдарламалау тіліне айналдырды. Нәтижесінде "сыныптары бар Си" с++деп аталды. Содан бері екі тіл де бір-біріне тәуелсіз дами бастады.

С++ - бұл Си-ден жадпен жұмыс істеудің бай мүмкіндіктерін мұра ететін қуатты тіл. Сондықтан, с++ көбінесе жүйелік бағдарламалауда, атап айтқанда операциялық жүйелерді, драйверлерді, әртүрлі утилиталарды, антивирустарды және т.б. құру кезінде қолданылады. Бірақ бұл тілді қолдану тек жүйелік бағдарламалаумен шектелмейді. С++ бағдарламасын жұмыс жылдамдығы мен өнімділігі мауды кез-келген деңгейдегі бағдарламаларда қолдануға болады. Көбінесе ол графикалық қосымшаларды, әртүрлі қолданбалы бағдарламаларды жасау үшін қолданылады. Сондай-ақ, ол бай визуализациясы бар ойындар жасау үшін жиі қолданылады. Сонымен қатар, жақында мобильді бағыт пайда болды, онда С++ де оны қолдануды тапты. Тіпті веб-әзірлеуде де веб-қосымшаларды немесе веб-қосымшаларға қызмет көрсететін кейбір көмекші қызметтерді құру үшін c++ тілін қолдануға болады. Жалпы, с++ - кез-келген бағдарламаны жасауға болатын кең қолданылатын тіл.

С++ - Бұл құрастырылатын тіл,яғни компилятор бастапқы кодты с++ тіліне машиналық нұсқаулар жиынтығын қамтитын орындалатын файлға жібереді. Бірақ әр түрлі платформалардың өзіндік ерекшеліктері бар, сондықтан құрастырылған бағдарламаларды бір платформадан екіншісіне ауыстырып, сол жерде іске қосу мүмкін емес. Алайда, бастапқы код деңгейінде c++ бағдарламалары, егер ағымдағы ОЖ-ге тән функциялар қолданылмаса, көбірек төзімділікке ие болады. Барлық кең таралған платформаларға арналған компиляторлардың, кітапханалардың және әзірлеу құралдарының болуы бірдей бастапқы кодты с++ тілінде осы платформаларға арналған қосымшаларға құрастыруға мүмкіндік береді.

С - тен айырмашылығы, C++ тілі бағдарламаны өзара әрекеттесетін сыныптар мен объектілердің жиынтығы ретінде ұсына отырып, объектіге бағытталған стильде қосымшалар жазуға мүмкіндік береді. Бұл үлкен қосымшаларды құруды жеңілдетеді.

Дамудың негізгі кезеңдері

1979-80 жылдары Бьерн Страуструп Си тіліне - "сыныптары бар Си"кеңейтімін жасады. 1983 жылы Тіл c++деп өзгертілді.

1985 жылы С++ тілінің алғашқы коммерциялық нұсқасы, сондай-ақ "C++ бағдарламалау тілі" кітабының алғашқы басылымы шығарылды, ол ресми стандарт болмаған кезде осы тілдің алғашқы сипаттамасын ұсынды.

1989 жылы C++ 2.0 тілінің жаңа нұсқасы шығарылды, оған бірқатар жаңа мүмкіндіктер енгізілді. Осыдан кейін тіл 2011 жылға дейін салыстырмалы түрде баяу дамыды. Бірақ бұл ретте 1998 жылы ISO (International Organiztion for Standartization) ұйымы тілді стандарттау бойынша алғашқы әрекет жасады. Бірінші стандарт ISO/IEC 14882:1998 немесе қысқартылған c++98 деп аталды. Кейіннен 2003 жылы c++03 стандартының жаңа нұсқасы жарық көрді.

2011 жылы жаңа C++11 стандарты шығарылды, онда көптеген қосымшалар бар және С++ тілін көптеген жаңа функционалдылықпен байытады. Осыдан кейін, 2014 жылы стандартқа аздап қосымша шығарылды, ол C++14 деп те аталады. Тілдің тағы бір негізгі шығарылымы 2017 жылға жоспарланған.

Компиляторлар және даму ортасы

С++ бағдарламаларын жасау үшін компилятор қажет-ол бастапқы кодты с++ тілінде орындалатын файлға жібереді, оны кейін іске қосуға болады. Бірақ қазіргі уақытта әртүрлі компиляторлар көп. Олар әртүрлі аспектілерде, атап айтқанда стандарттарды іске асыруда ерекшеленуі мүмкін. С++ үшін компиляторлардың негізгі тізімін Википедиядан көруге болады. Әзірлеу үшін барлық соңғы стандарттарды дамытатын және жүзеге асыратын компиляторларды таңдау ұсынылады. Сонымен, нұсқаулық барысында GNU жобасы аясында жасалған еркін таратылатын G++ компиляторы негізінен қолданылады.

Сондай-ақ, бағдарламаларды құру үшін Visual Studio, Netbeans, Eclipse, Qt және т. б. сияқты ide интеграцияланған даму ортасын пайдалануға болады

1.2.1 С++ тілінің негізгі операторлары
C++ – Операторлар

Оператор – компиляторға белгілі бір математикалық немесе логикалық манипуляцияларды орындауға нұсқау беретін символ. C++ кірістірілген операторларға бай және операторлардың келесі түрлерін қамтамасыз етеді:

1. 
   Арифметикалық операторлар
   
2. 
   Реляциялық операторлар
   
3. 
   Логикалық операторлар
   
4. 
   Биттік операторлар
   
5. 
   Тағайындау операторлары
   
6. 
   Басқа операторлар
   

Кесте 1.1

Арифметикалық операторлар

Оператор	Сип9аттама	Мысал
+	Екі операнд қосады	A + B 30 береді
-	Біріншіден екінші операндты шегереді	A - B -10 береді
*	Екі операндты да көбейтеді	A * B 200 береді
/	Алымды азайтқышқа бөледі	B/A 2 береді
%	Модуль операторы және бүтін санды бөлуден кейінгі қалдық	B%A 0 береді
++	Көбейту операторы бүтін мәнді бір көбейтеді	A++ 11 береді
-	Бүтін мәнді бір азайтады	A-- 9 береді

Кесте 1.2

Реляциялық операторлар

Оператор	Сипаттама	Мысал
==	Екі операндтың мәндерінің тең немесе тең еместігін тексереді, иә болса, шарт ақиқатқа айналады.	(A == B) дұрыс емес.
=	Екі операндтың мәндерінің тең немесе тең еместігін тексереді, егер мәндер тең болмаса, шарт ақиқатқа айналады.	(A!=B) дұрыс.
>	Сол операндтың мәні оң операндтың мәнінен үлкен екенін тексереді, егер солай болса, шарт ақиқатқа айналады.	(A>B) қате.
<	Сол операндтың мәні оң операндтың мәнінен аз екенін тексереді, егер солай болса, шарт ақиқатқа айналады.	(A
Кесте 1.2 жалғасы
>=	Сол операндтың мәні оң операндтың мәнінен үлкен екенін тексереді, егер солай болса, шарт ақиқатқа айналады.	(A>=B) дұрыс емес.
<=	Сол операндтың мәні оң операндтың мәнінен аз немесе тең болса, тексереді, егер солай болса, онда шарт ақиқат болады.	(A <= B) дұрыс.

Кесте 1.3

Разрядтық операторлар

Оператор	Сипаттама	Мысал
&	Екілік ЖӘНЕ операторы екі операндта да бар болса, нәтижеге аздап көшіреді.	(A & B) 0000 1100 болатын 12 береді
|	Екілік НЕМЕСЕ операторы операндтардың кез келгенінде бар болса, битті көшіреді.	(A | B) 61 береді, бұл 0011 1101
^	Екілік XOR операторы бір операндқа орнатылған болса, бірақ екеуі де емес, битті көшіреді.	(A^B) 49 береді, бұл 0011 0001
~	Екілік бірліктер Толықтауыш операторы біртұтас және биттерді «аудару» әсерін береді.	(~A) таңбалы екілік санға байланысты 2 толықтауыш түрінде 1100 0011 болатын -61 мәнін береді.
<<	Екі рет солға жылжыту операторы.Сол жақ операндтардың мәні оң жақ операндпен көрсетілген бит санымен солға жылжиды.	A << 2 240 береді, бұл 1111 0000
>>	Екілік оңға жылжу операторы. Сол жақ операндтардың мәні оң жақ операндпен көрсетілген биттердің санына қарай жылжытылады.	A >> 2 0000 1111 болатын 15 береді

Кесте 1.4

Кесте 1.5

Басқа операторлар

Оператор	Сипаттама
sizeof	Айнымалының өлшемін қайтарады. Мысалы sizeof(a) мұндағы 'a' бүтін сан және 4 қайтарады.
Шарты? X : Y	Шарт ақиқат болса, ол X мәнін қайтарады, әйтпесе Y мәнін қайтарады.
,	Әрекеттер тізбегін шақырады. Бүкіл үтір өрнектің мәні үтірмен бөлінген тізімдегі соңғы өрнектің мәні болып табылады.
. (нүкте) және -> (көрсеткі)	Сыныптардың, құрылымдардың және одақтардың жекелеген мүшелеріне сілтеме жасау үшін қолданылады.
Cast	Бір деректер түрін екіншісіне түрлендіру. Мысалы, int(2.2000) 2 қайтарады.
&	Айнымалының мекенжайын қайтарады. Мысалы, &a; айнымалының нақты мекенжайын береді.
*	Бұл айнымалыға көрсеткіш. Мысалы *var; айнымалыға нұсқайды.

C++ тіліндегі оператордың басымдығы

Оператордың басымдығы өрнектегі терминдердің топтастырылуын анықтайды. Бұл өрнекті бағалауға әсер етеді. Кейбір операторлар басқаларға қарағанда жоғары басымдыққа ие; мысалы, көбейту операторының қосу операторына қарағанда басымдығы жоғары -

Мысалы, x = 7 + 3 * 2; мұнда х 20 емес, 13-ке тағайындалады, себебі * операторының +-ге қарағанда басымдығы жоғары, сондықтан оны алдымен 3*2-ге көбейтіп, сосын 7-ге қосады.

Мұнда басымдылығы жоғары операторлар кестенің жоғарғы жағында, ал ең төменгі басымдығы бар операторлар төменгі жағында пайда болады. Өрнек ішінде бірінші кезекте жоғарырақ операторлар бағаланады.

Басымдылығы жоғары операторлар

1.2.2 Массивтер

T a[N];

Мұндай массивтерді массивтердің басқа нұсқаларынан айырмашылығын атап өту үшін кірістірілген массивтер (regular arrays) деп те атайды, "массив" термині бағдарламалауда, соның ішінде C++ тілінде де қолданылады.

Мұнда дұрыс массив жарнамаларының мысалдары келтірілген:
const int N = 8;

constexpr int Square(int n) { return n * n; }

int a1[1];

int a2[N];

int a3['Q'];

int a4[Square(2)];

Бірақ массивтердің дұрыс емес жарнамаларының мысалдары:

int n;

int b2 [n]; / / компиляция кезінде өлшемді анықтау мүмкін емес

int b3 ["Q"]; / / өлшемі size_t-ге әкелмейді

Массив элементтеріне индексатор арқылы қол жеткізуге болады, индекс мәні 0-ден N-1-ге дейін. Міне мысал:

int a[4];

a[0] = 42;

int t = a[3];

Массивтің шекарасынан шығу бақыланбайды, қате белгісіз мінез-құлыққа әкелуі мүмкін.

Бір нұсқаулықта бірнеше массивтерді жариялауға болады, бірақ мөлшері әрқайсысына көрсетілуі керек.

int a[4], b[8];

1. 
   Көрсеткіштер
   

Компилятор айнымалы анықтау операторын өңдеген кезде, мысалы, int i=10;, ол жад түріне (int) сәйкес бөлінеді және оны көрсетілген мәнге (10) инициализациялайды. Бағдарламадағы айнымалыға оның аты (i) бойынша барлық өтініштер компилятормен айнымалы мәні сақталатын жад аймағының мекен-жайына ауыстырылады. Бағдарламалаушы жад аймағының мекен-жайларын сақтау үшін жергілікті айнымалыларды анықтай алады. Мұндай айнымалылар көрсеткіштер деп аталады.

Сонымен, көрсеткіштер жад аймағының мекен-жайларын сақтауға арналған. C++ тілінде көрсеткіштердің үш түрі бар:

нысанға көрсеткіштер,

функция көрсеткіштері

void көрсеткіштері,

garantx.ru

Функция көрсеткіші

Функция сілтегішінде функцияның орындалатын коды орналасқан код сегментіндегі мекен-жай, яғни функция шақырылған кезде басқару жіберілетін мекен-жай бар. Функция көрсеткіштері функцияны жанама шақыру үшін (оның аты арқылы емес, оның мекен-жайын сақтайтын айнымалыға жүгіну арқылы), сондай-ақ функция атауын параметр ретінде басқа функцияға беру үшін қолданылады. Функция сілтегіші "берілген типтің мәнін қайтаратын және берілген типтегі дәлелдері бар функция сілтегіші"типіне ие:

түрі (*аты) (тізім_типов_аргументов);

Мысалы, хабарландыру:

nt (*fun) (double, double);

fun деп аталатын көрсеткішті int типінің мәнін қайтаратын және қос типтегі екі аргументі бар функцияға орнатады.

Нысанға көрсеткіш

Нысанның сілтемесінде белгілі бір типтегі (негізгі немесе құрама) деректер сақталатын жад аймағының мекен-жайы болады. Нысанға көрсеткіштің қарапайым декларациясы (бұдан әрі жай көрсеткіш деп аталады):

түрі * аты;

түрі Сілтеме мен бит өрісінен басқа кез-келген жерде болуы мүмкін, бұл кезде түрі тек жариялануы мүмкін, бірақ әлі анықталмаған (сондықтан құрылымда, мысалы, сол типтегі құрылымға сілтегіш болуы мүмкін).

Жұлдызша тікелей атқа жатады, сондықтан бірнеше белгілерді жариялау үшін оны әрқайсысының есімінің алдына қою керек. Мысалы, операторда

int *a, b, *c;

А және с атаулары бар бүтін екі көрсеткіш, сондай-ақ B айнымалысы сипатталған.

Көрсеткіш өлшемі жад моделіне байланысты. Меңзерді меңзерге және т. б. анықтауға болады.

1.2.3 Көрсеткіштер

Көрсеткіш – мәні жад орнының мекенжайы болып табылатын айнымалы. Яғни, көрсеткіш жад аймағынан деректер блогына және оның ең басына жатады. Көрсеткіш айнымалыға немесе функцияға сілтеме жасай алады. Ол үшін айнымалының немесе функцияның адресін білу керек. Сонымен, C++ тілінде белгілі бір айнымалының адресін білу үшін & адресін алудың біртұтас операциясы бар. Мұндай операция көрсеткішке тағайындау үшін жарияланған айнымалылардың мекенжайын шығарады.

Көрсеткіштер мәліметтерді сілтеме бойынша беру үшін пайдаланылады, бұл бұл деректерді өңдеу процесін айтарлықтай жылдамдатады (деректер көлемі үлкен болған жағдайда), өйткені оларды мән бойынша өту кезіндегідей көшіру қажет емес, яғни айнымалы атауы. Негізінде көрсеткіштер жадтың динамикалық бөлінуін ұйымдастыру үшін пайдаланылады, мысалы, массивті жариялағанда, оны өлшемде шектеу қажет болмайды. Өйткені, бағдарламашы белгілі бір пайдаланушы үшін массивтің қандай өлшемді қажет ететінін алдын ала біле алмайды, бұл жағдайда массив үшін динамикалық жадты бөлу қолданылады. Кез келген көрсеткішті кез келген айнымалы сияқты пайдалану алдында жариялау керек.

CppStudio.com

&var = 0x22ff08

ptrvar=0x22ff08

var=123

*ptvar = 123

Жалғастыру үшін кез келген пернені басыу. . .

1-сурет - C++ тіліндегі көрсеткіштер

Сонымен, бағдарлама 11 және 12-жолдар бірдей адресті, яғни ptrvar көрсеткішінде қамтылған айнымалының адресін шығаратынын көрсетті. Ал *ptrvar көрсеткішін жою операциясы көрсеткішпен көрсетілген мәнге қол жеткізуді қамтамасыз етеді.

Көрсеткіштерді тек теңдік немесе теңсіздік үшін ғана салыстыруға болмайды, өйткені мекенжайлар бір-біріне қатыстыдан кіші немесе үлкен болуы мүмкін. Көрсеткіш адрестерін салыстыратын бағдарлама әзірлейік.

2 Сұрыптау және іздеу алгоритмдеріне шолу

Сұрыптау әдетте массив элементтерінің жұптарын қайта салыстыру және егер олар берілген өлшемдерге сәйкес келсе, мәндерді ауыстыру арқылы жүзеге асырылады. Бұл элементтердің салыстырылатын реті қай сұрыптау алгоритмі қолданылатынына байланысты. Критерийлер массивтің қалай сұрыпталатынын анықтайды (мысалы, өсу ретімен немесе кему ретімен).

#include

# include // std үшін:: ауыстыру. C++11-де тақырыбын қолданыңыз

int main()

{

int a = 3;

std::cout << "Before swap: a = " << a << ", b = " << b << '\n';

std:: swap (a, b); / / A және b айнымалыларының мәндерін ауыстырамыз

std::cout << "After swap: a = " << a << ", b = " << b << '\n';

}

Бағдарламаны орындау нәтижесі:

After swp: a = 5, b = 3

Ауыстыру әрекетін орындағаннан кейін A және b айнымалыларының мәндері өзгерді.

2.1 Қарапайым алмасу әдісі арқылы сұрыптау

Солдан оңға қарай екі көрші элемент кезекпен салыстырылады, ал егер олардың өзара орналасуы берілген тапсырыс шартына сәйкес келмесе, онда олар ауысады. Әрі қарай, келесі екі көрші элемент алынады және массивтің соңына дейін.

Осындай бір өтуден кейін массивтің N-ші позициясында максималды (немесе минималды) элемент болады (бірінші"көпіршік" "пайда болды"). Максималды (немесе минималды) элемент өзінің соңғы позициясында болғандықтан, Биржаның екінші өтуі (n-1) элементіне дейін орындалады. Және олай бұдан әрі. Барлығы (n-1) өту қажет.

Тапсырма. Дәптерде кездейсоқ таңдалған массивтің қарастырылған алгоритмінің жұмыс сызбасын сызыңыз.

Жоғарыда қарастырылған алгоритмді жүзеге асыратын процедураны қарастырыңыз:

Obmen процедурасы(Var a : Array1);

Var

i, j,f, g:бүтін сан;

i-ден:=n-ден 2 do-ға дейін

J үшін:=1-ден i-1-ге дейін жасаңыз

егер a[j]>a [j + 1]

сонда

бастаңдар

a[j]:=a[j+1];

a[j+1]:=f;

соңы;

Тапсырма. Қарастырылған әдіспен бір өлшемді массивті сұрыптау бағдарламасын жасаңыз.

Массивті Рекурсия арқылы сұрыптау

Массив мәндерін сұрыптау алгоритмін құру үшін рекурсияны қолдануды қарастырыңыз.

Алгоритм келесідей жүзеге асырылады: массивтің белгілі бір сегментінде орталық (ортаңғы) мән таңдалады; кесіндінің сол жағындағы орталық мәннен асатын барлық элементтер оң жаққа ауысады және керісінше. Келесі қадамда (сол процедураның рекурсивті қоңыраулары қолданылатын) алгоритм сегменттің екі бөлігі үшін де қайталанады.

Массив массивінен сол жақ индекстер диапазонындағы мәннің өсуіне байланысты процедураны қарастырыңыз..

Оң жақта.

Жылдам сұрыптау процедурасы (сол, оң: бүтін сан; Массив: Массив1);

Var

Procedure QuickSort (Left, Right : integer; Massiv : Array1);

i, j, x, y : integer;

Begin

i := Left;

x := Massiv[(Left+Right) div 2];{}

repeat

while Massiv[i]

Inc(i);

while Massiv[j]>x do

Dec(j);

if i<=j

begin

Massiv[i] := Massiv[j];

Massiv[j] := y;

Inc(i);

end;

if Left

then

QuickSort (Left, j);